有100万个数字（1到9），其中只有1个数字重复2次，如何快速找出该数字

hq8318

这令我想起，以前当一副扑克多了一张相同底色的牌时，为了找出那张牌，一张张发，按点数分成一堆堆，当那一堆的牌超出时，那张就是多余的了！这题也可用类似的算法，比如一万个数，一百个一组，将数据大小加到1百、或2百、或3百……里，当那组超出一百，就在那组里，再递归找出来。

hq8318

哈希表、有序图在存入值时，也要判断key是否相同，找到那个key，就保存，无就新建。只不过是这些已封装好，不用理，当然已优化好了。如不用高级类型，我只想到一算法:排序，再遍历--比较相邻两数是否相等，等就是那个了。

hq8318

回复 35# mirnshi

网上查到------
    Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合。
　 这题判断时要求100%正确，不适用吧。

hq8318

“如果必须是100%，可以在冲突后，再进行循环检索”，这样就不是“小case，用bloom filter轻松搞定”吧。

hq8318

　　CSDN更多人讨论，原来这题是指“题目 意思：我这里每个数字都是一个阿拉伯数字 是1位的 是 1到9之间的 但是有1百万个这样的数字 比如 12345678912 是11个这样的数字”。
　　我思路大概是：当数字出现3次直接忽略，8个数字出现3次时结束。
　　用图m 保存数字出现的次数，出现3次的保存到一集合hs，并从m 中移出。集合hs有的数字，不用比较了，直接跳到下一个，当集合hs有8个数字时，输出结果。最后是当hs达不到8个数字时，找到只出现两次的数字，输出，由于集合无indexOf,只有用一循环。

1. 
   
2. import java.util.*;
   
3. public class million
   
4. {
   
5.   public static void main(String args[])
   
6.     {
   
7.           int[] n={1,2,3,3,4,5,6,7,8,9,3,1,5,6,5,6,3,7,8,9,7,8,9,2,2,4,4};
   
8.           // int[] n={1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,1,2,3,1,5,6,7,8,9};
   
9.           // int[] n={1,2,3,4,5,6,7,8,9,1,2,2,2};
   
10.           Map<Integer,Integer> m=new HashMap<Integer,Integer>();
    
11.           Set<Integer> hs=new HashSet<Integer>();
    
12.           Integer v;
    
13.           for(int n1:n){                    
    
14.                     if(hs.contains(n1)) continue;
    
15.                     v=m.get(n1);
    
16.                     if(v==null)
    
17.                                 m.put(n1,1);
    
18.                     else if(v==1)
    
19.                                 m.put(n1,v+1);
    
20.                     else if(v==2){
    
21.                                 hs.add(n1);                                
    
22.                                 m.remove(n1);
    
23.                                 if(hs.size()==8){
    
24.                                           for(int i=1;i<10;i++){
    
25.                                                     if(!hs.contains(i)) System.out.println(i);
    
26.                                           }
    
27.                                           break;
    
28.                                 }
    
29.                     }
    
30.           }
    
31.           if(hs.size()<8){
    
32.                     for(Integer k:m.keySet()){
    
33.                                 if(m.get(k)==2)
    
34.                                           System.out.println(k);
    
35.                     }
    
36.           }
    
37.           System.out.println(m);
    
38.           System.out.print(hs);
    
39.     }
    
40. }

复制代码