Chinaunix

标题: 有100万个数字（1到9），其中只有1个数字重复2次，如何快速找出该数字 [打印本页]
作者: qishking    时间: 2011-08-04 09:02
标题: 有100万个数字（1到9），其中只有1个数字重复2次，如何快速找出该数字
在CSDN上看到的，有点意思，有啥好办法？
作者: starwing83    时间: 2011-08-04 09:14
1到9？100万？那么每个数字至少得出现10万次吧？？
作者: peidright    时间: 2011-08-04 09:17
遍历一遍, 关健是遍历过程中, 每新发現一个肯定不是解,就时刻注意当前还可能为解的数目.
极端情形下,没啥好办法.

比如
前999998 为某个整数, 最后2个为某个整数.

看上去这题目没啥意思,o(n)不可避免
作者: jeung    时间: 2011-08-04 09:24
回复 3# peidright


    问题是这个“新”字
作者: starwing83    时间: 2011-08-04 09:51
遍历一遍, 关健是遍历过程中, 每新发現一个肯定不是解,就时刻注意当前还可能为解的数目.
极端情形下,没啥好 ...
peidright 发表于 2011-08-04 09:17



    你在O(1)的空间下，能做到O(n)的复杂度？？在没有特殊的算法的前提下（如异或）可能么？
作者: goldenfort    时间: 2011-08-04 10:01
回复 1# qishking


    没有实用价值，编造的题目， 是shit.
作者: peidright    时间: 2011-08-04 11:02
回复 5# starwing83


    , 这里我的O(n)的意思是1000000, 不是 10., 搞个uint8 a[10]; 直接数就行了.
    一点点的工程義義就是, 当以经发现9个大与2的情况, 就直接可以得到必然另外那个数是xx
    应该是道没任何義义的题目
作者: starwing83    时间: 2011-08-04 11:10
回复 7# peidright


    如果只有1~9九个数字，肯定没意义，我回过了，但是假设有999999个各不相同的32位数，有一个数字和前面的一个数字重复，请问如何找到这个重复的数字呢？
作者: peidright    时间: 2011-08-04 11:46
回复 8# starwing83


    没办法.!
作者: starwing83    时间: 2011-08-04 12:23
回复 9# peidright


    是这样的，我以前好像看过类似的题目，有一个很巧妙的异或的解法。我去matrix67的博客找找……
作者: starwing83    时间: 2011-08-04 12:41
回复 10# starwing83


    我记错了…………那个解法是针对求仅有一个数出现过奇数次的…………
作者: linux_kaige    时间: 2011-08-04 14:42
10w个，只有一个重复的，从复杂度上来讲，肯定要遍历一边的，0—n，前两个相同，或第一跟最后一个相同。
由于你的数字太多，shell的数组最大为1024，肯定容不下了，我不知道我写这个行不行。假设你的数字间的分隔符为空格：
sed 's/\ /\n/g' filename | uniq -d
作者: ilwmin    时间: 2011-08-04 16:23
微软面试题
作者: hidensu    时间: 2011-08-04 19:33
回复 1# qishking


    我的思路是以空间换时间，其实未必要一个一个数字去比，而可以比如2位一组去比，需要的空间也就81，按照此思路，时间复杂度完全不用0(n)，希望哪位高手来实现下
作者: starwing83    时间: 2011-08-04 20:12
回复 15# hidensu


    这位大神请问您知道啥叫时间复杂度吗？
作者: hidensu    时间: 2011-08-05 10:48
回复 16# starwing83


    时间复杂度没变，呵呵，不过可以很大提高效率，一次对比未必要一个一个数字对比，一次只对比一个数字是最大的浪费
作者: starwing83    时间: 2011-08-05 13:14
回复 17# hidensu


    “很大提高效率”？有测试过？常数多少？具体算法？你以为只两个两个比就可以了？这个世界上不是所有的划分算法都是可以两个两个比的。
作者: fender0107401    时间: 2011-08-05 13:18
回复  peidright


    如果只有1~9九个数字，肯定没意义，我回过了，但是假设有999999个各不相同的32位 ...
starwing83 发表于 2011-08-04 11:10


和统计词频应该是一样的吧，trie不就行了吗？
作者: fender0107401    时间: 2011-08-05 13:20
回复  qishking


    我的思路是以空间换时间，其实未必要一个一个数字去比，而可以比如2位一组去比， ...
hidensu 发表于 2011-08-04 19:33


O(n)=O(constant*n)
作者: yulihua49    时间: 2011-08-05 13:25
本帖最后由 yulihua49 于 2011-08-05 13:29 编辑
回复  peidright


    如果只有1~9九个数字，肯定没意义，我回过了，但是假设有999999个各不相同的32位 ...
starwing83 发表于 2011-08-04 11:10



    插入二叉树，发现重码的节点就是了。复杂度：
O（log2(N))
这题目的意义在于，一个数据库，里边有了1000000数据，新加入一个数据，如何最快判断出重码？答曰：建立唯一索引。
hash树也可以。
作者: starwing83    时间: 2011-08-05 18:05
LS：您的方法都要求空间复杂度O(N)，我想知道能不能在空间复杂度O(1)的前提下搞定
作者: qiangtoucao121    时间: 2011-08-06 16:12
以空间换时间
作者: chockly    时间: 2011-08-07 09:20
本帖最后由 chockly 于 2011-08-07 09:25 编辑

int FindTheDigit(int arr[], int len)
{
        int tmp[10];        //用于统计数字出现次数
        int i,j;
        int above2 = 0;                   
        int flag = false;
        //初始化
        for(i=0; i<10; i++)
                tmp = 0;
        //开始遍历
        for(i=0; i<len; i++)
        {
                if(tmp[arr] < 3)
                        tmp[arr]++;
                above2 = 0;
                for(j=1; j<10; j++)
                        if(tmp[j] > 2)
                                above2++;
                //如果有8个数字出现次数大于2次，停止遍历
                if(above2 >= 8 )
                {
                        flag = true;
                        break;
                }
        }
       
        if(flag)
        {
                for(i=1; i<10; i++)
                        if(tmp <= 2)
                                return i;
        }
        else
        {
                for(i=1; i<10; i++)
                        if(tmp == 2)
                                return i;
        }
        return 0;
}
作者: 337240552    时间: 2011-08-08 08:25
提示: 作者被禁止或删除 内容自动屏蔽
作者: 157284    时间: 2011-08-08 09:44
用集合或哈希表，因为相同key自动覆盖，而它的size 不会增加。恰巧 javascript的 Array实际上就是一个哈希表,属性名称就是哈希表的key，而属性的值就是哈希表的值。由于各人使用的语言可能不同，下面用javascript 写了写，方便大家调试。当表的长度不增加，那个就是不同的值了。
  1. <script type="text/javascript">
  2. var i,arr=[],arr1=[];
  3. for (i=1;i<100;i++) arr[i]=i;
  4. arr[50]=22;
  5. var L=0;
  6. for(n in arr)
  7. {
  8.           arr1[arr[n]]=arr[n];
  9.           if(arr1.length==L) {alert(arr[n]);break;}
  10.           else L=arr1.length;
  11. }
  12. </script>
复制代码
作者: hq8318    时间: 2011-08-08 10:20
这令我想起，以前当一副扑克多了一张相同底色的牌时，为了找出那张牌，一张张发，按点数分成一堆堆，当那一堆的牌超出时，那张就是多余的了！这题也可用类似的算法，比如一万个数，一百个一组，将数据大小加到1百、或2百、或3百……里，当那组超出一百，就在那组里，再递归找出来。
作者: 157284    时间: 2011-08-08 11:12
恰巧PHP 中的数组实际上是一个有序图，26楼的代码修改下，就成了PHP的，至于C++、JAVA有很多高级数据类型，更方便了。
  1. <?php
  2. $arr=array();$arr1=array();
  3. for ($i=1;$i<100;$i++) $arr[$i]=$i;
  4. $arr[10]=13;
  5. $L=0;
  6. foreach($arr as $n)
  7. {
  8.           $arr1[$n]=$n;
  9.           if(count($arr1)==$L) {echo($n);break;}
  10.           else $L=count($arr1);
  11. }
  12. ?>
复制代码
作者: hq8318    时间: 2011-08-08 11:21
本帖最后由 hq8318 于 2011-08-08 11:25 编辑

哈希表、有序图在存入值时，也要判断key是否相同，找到那个key，就保存，无就新建。只不过是这些已封装好，不用理，当然已优化好了。如不用高级类型，我只想到一算法:排序，再遍历--比较相邻两数是否相等，等就是那个了。
作者: kgdvoso    时间: 2011-08-08 23:25
二分查找、、
作者: rdcwayx    时间: 2011-08-09 09:29
用awk 的话，不知道效率如何。
  1. awk '++a[$1]==2{print $1;exit}' infile
复制代码
作者: cjaizss    时间: 2011-08-09 19:38
LS：您的方法都要求空间复杂度O(N)，我想知道能不能在空间复杂度O(1)的前提下搞定
starwing83 发表于 2011-08-05 18:05



    O(1)空间前提下,应该不存在O(n)级时间.
作者: starwing83    时间: 2011-08-10 10:42
回复 32# cjaizss


    很有趣的问题：偶选奇可以用异或法达到O(1)的空间复杂度和O(n)的时间复杂度，然而嘛……奇选偶却无法用O(1)的空间复杂度达到O(n)的时间复杂度？？这个是什么原因呢？
作者: yuxh    时间: 2011-08-14 09:30
cjaizss 说得没错，此问题不可能存在O(1)空间，O(n)时间复杂度的算法
原因在于，无法用O(1)的空间包含“O(n)个数各不相同”这一信息
除非数据有特殊的规律
作者: mirnshi    时间: 2011-08-14 12:11
不用说100万个数字了，就是100万个字符串，也是小case，用bloom filter轻松搞定。
作者: hq8318    时间: 2011-08-14 22:33
回复 35# mirnshi

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

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


1. 多重哈希可以降低冲突
2. 如果必须是100%，可以在冲突后，再进行循环检索。这个空间和时间要求都能很好的掌控了。
作者: hq8318    时间: 2011-08-15 14:14
“如果必须是100%，可以在冲突后，再进行循环检索”，这样就不是“小case，用bloom filter轻松搞定”吧。
作者: mirnshi    时间: 2011-08-15 15:36
“如果必须是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    时间: 2011-08-16 01:20
本帖最后由 hq8318 于 2011-08-16 01:28 编辑

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

  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. }
复制代码




欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2