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

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

评论

29 楼 X13144131X 2012-10-03  

cx372877498 写道

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

当时他就是这个意思，对算法不怎么行，如果个数任然是100W零1个，但是数值上并没有特殊的规律，确实不知道怎么搞好了，而且是要你把重复的取出来，效率那是再说

28 楼 cmdmg 2012-09-17  

此贴已沉啦

27 楼 xlaohe1 2012-09-13  

xlaohe1 写道

cmdmg 写道

copancn 写道

xlaohe1 写道

把所有数都加起来，然后减去1到100W的和得到那个数

这个是正确解啊，题目讲的很清楚，1-100W，找出唯一的重复数

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

你看清题吧：从1-100W的数据，中间有且只有一个重复的，个数为100W零1，找出来即可。

  好像是没说从1开始的。。。   

26 楼 xlaohe1 2012-09-13  

cmdmg 写道

copancn 写道

xlaohe1 写道

把所有数都加起来，然后减去1到100W的和得到那个数

这个是正确解啊，题目讲的很清楚，1-100W，找出唯一的重复数

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

你看清题吧：从1-100W的数据，中间有且只有一个重复的，个数为100W零1，找出来即可。

25 楼 cmdmg 2012-09-13  

copancn 写道

xlaohe1 写道

把所有数都加起来，然后减去1到100W的和得到那个数

这个是正确解啊，题目讲的很清楚，1-100W，找出唯一的重复数

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

24 楼 copancn 2012-09-13  

xlaohe1 写道

把所有数都加起来，然后减去1到100W的和得到那个数

这个是正确解啊，题目讲的很清楚，1-100W，找出唯一的重复数

23 楼 xlaohe1 2012-09-13  

把所有数都加起来，然后减去1到100W的和得到那个数

22 楼 ilrxx 2012-09-13  

21 楼 cnlinkin 2012-09-13  

leaow567 写道

bitset呢？

agreed,创建一个100Wbit长的bitset，将这100w+1个数据映射到每个slot中，直到出现碰撞为止。映射函数用n mod 100W

20 楼 zzk7811 2012-09-13  

二分法查找就成

19 楼 闪闪4521 2012-09-13  

闪闪4521 写道

编程珠玑第一章开篇就是这个例子，只不过他说的是排序电话号码...
如果找出一个相同的，要最坏情况也只需要遍历一遍就行了，时间复杂度O(n)

所以面试前先把一些经典的书复习一下啊

18 楼 kfc_davy 2012-09-13  

jeschou 写道

Eddic 写道

flatcsun 写道

如果用java的话可以用集合实现，遍历一遍就好了。

Set set = new HashSet();
Object repeatObj = null;//重复的数据
for(int i=0; i<array.length; i++){
    if(set.contains(array[i]){
        repeatObj = array[i];
        break;
    }else{
        set.add(array[i]);
    }
}

set.contains()里边也要遍历的呀

HashSet不会遍历，它是用hash算法直接计算元素位置
HashSet的contains方法效率是非常高的

另外，因为数据量已知,100W,可以在构造HashSet的时候加一些参数,以进一步提高性能

效率是高，不认为的话哈希碰撞也不大会，但是百万级甚至千万级别以上，都放到一个map中合适吗

17 楼 闪闪4521 2012-09-13  

编程珠玑第一章开篇就是这个例子，只不过他说的是排序电话号码...
如果找出一个相同的，要最坏情况也只需要遍历一遍就行了，时间复杂度O(n)

16 楼 jeschou 2012-09-13  

Eddic 写道

flatcsun 写道

如果用java的话可以用集合实现，遍历一遍就好了。

Set set = new HashSet();
Object repeatObj = null;//重复的数据
for(int i=0; i<array.length; i++){
    if(set.contains(array[i]){
        repeatObj = array[i];
        break;
    }else{
        set.add(array[i]);
    }
}

set.contains()里边也要遍历的呀

HashSet不会遍历，它是用hash算法直接计算元素位置
HashSet的contains方法效率是非常高的

另外，因为数据量已知,100W,可以在构造HashSet的时候加一些参数,以进一步提高性能

15 楼 xlaohe1 2012-09-13  

直接异或。

14 楼 leaow567 2012-09-13  

bitset呢？

13 楼 ylsun1113 2012-09-13  

这个不能用Java，要用sql实现。用group by + having count(*)>1实现

12 楼 gqsunrise 2012-09-13  

亲，直接group by然后having不行么？

11 楼 Eddic 2012-09-13  

flatcsun 写道

如果用java的话可以用集合实现，遍历一遍就好了。

Set set = new HashSet();
Object repeatObj = null;//重复的数据
for(int i=0; i<array.length; i++){
    if(set.contains(array[i]){
        repeatObj = array[i];
        break;
    }else{
        set.add(array[i]);
    }
}

set.contains()里边也要遍历的呀

10 楼 flatcsun 2012-09-13  

如果用java的话可以用集合实现，遍历一遍就好了。

Set set = new HashSet();
Object repeatObj = null;//重复的数据
for(int i=0; i<array.length; i++){
    if(set.contains(array[i]){
        repeatObj = array[i];
        break;
    }else{
        set.add(array[i]);
    }
}