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

rdcwayx

用awk 的话，不知道效率如何。

1. awk '++a[$1]==2{print $1;exit}' infile

复制代码

cjaizss

LS：您的方法都要求空间复杂度O(N)，我想知道能不能在空间复杂度O(1)的前提下搞定
starwing83 发表于 2011-08-05 18:05

    O(1)空间前提下,应该不存在O(n)级时间.

starwing83

回复 32# cjaizss


    很有趣的问题：偶选奇可以用异或法达到O(1)的空间复杂度和O(n)的时间复杂度，然而嘛……奇选偶却无法用O(1)的空间复杂度达到O(n)的时间复杂度？？这个是什么原因呢？

yuxh

cjaizss 说得没错，此问题不可能存在O(1)空间，O(n)时间复杂度的算法
原因在于，无法用O(1)的空间包含“O(n)个数各不相同”这一信息
除非数据有特殊的规律

mirnshi

不用说100万个数字了，就是100万个字符串，也是小case，用bloom filter轻松搞定。

hq8318

回复 35# mirnshi

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

mirnshi

回复  mirnshi

网上查到------
    Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某 ...
hq8318 发表于 2011-08-14 22:33

1. 多重哈希可以降低冲突
2. 如果必须是100%，可以在冲突后，再进行循环检索。这个空间和时间要求都能很好的掌控了。

hq8318

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

mirnshi

“如果必须是100%，可以在冲突后，再进行循环检索”，这样就不是“小case，用bloom filter轻松搞定”吧。
hq8318 发表于 2011-08-15 14:14

Bloom filter可以极大降低空间时间复杂度。N多人研究过并且可以在网上找到成堆的论文，具体可以参考这些论文。

BTW，Bloom filter不适合题目要求（1到9，重复100万次，其中只有1个数字重复2次）。Bloom filter是针对楼上100万个不同数字提出的。

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. }

复制代码