百万数据去掉唯一重复的一个

今天面试的过程中，xxx公司的技术总监问了一个问题，本人觉得在某种情况下是可行的，但是貌似被否认了。求解释！

 

要求如下：从1-100W的数据，中间有且只有一个重复的，个数为100W零1，找出来即可。

 

我想的结果如下：假设数据是无序，但是1-100W之间有100W个数字，加上重复的一个，即100W零1.

 

步骤一、先将这100W零1按大小排序。

 

步骤二、首+尾=100W零1，取值往中间靠近。

 

步骤三、如果相加的和大于理论上的中间值（肯定是大于理论上的中间值）。则表示这两个数字中的一个必定是重复的。

 

然后分别用这两个数字，根据索引去取特定位置上的值来做判断即可得出。

 

如果题目是这样的，我觉得没错啊！

 

Q：如果100W条数据里面，只有一个是重复的，而且这些数值并不是像1、2、3、4...  这样，应该怎么去实现？

评论

9 楼 huoyunshen88 2012-09-13  

hadoop大数据处理。

8 楼 sharpice 2012-09-13  

主要还是性能问题，光排序100W个数就花掉不少时间了
提供一个算法不知道可行不，利用二叉树，从根节点开始比较，大的往右节点继续比较，小的往左节点比较。如果所比较的节点，已经没有子节点，则大的存放于右节点，小的存放于左节点。
这样类似于二分法查找，但不用排序，速度会快很多

7 楼 fulink 2012-09-13  

到底是数字还是数据？
这可是有差别的

6 楼 wangyanlong0107 2012-09-13  

主要考虑性能问题，100w的排序怎么排呢？

5 楼 flatcsun 2012-09-13  

第一步排序的过程中，要每个数据相互比较一次，比较的时候就可以把重复的找出来。

4 楼 kkppccdd 2012-09-13  

排序太慢了，最快也要O(nLogn)。用HASH表實現的Set，時間複杂度為O(n*O(hash()))，如果設計的hash算法的時間複杂度是常數，則縂複杂度為O(n)。

3 楼 worldterminator 2012-09-13  

排序即可。

2 楼 cx372877498 2012-09-12  

兄弟貌似题目你就理解错了，不是说是1到100w，就好像是100w到200w它也有100w个数字啊。就是这个数字不是一个有序的组合。

1 楼 hiqrf 2012-09-12  

101W个数相加 与 从1加到100W的差值 就是重复数的字