Chinaunix

标题: 从一百个数中找不存在的数 [打印本页]
作者: 发仔很忙    时间: 2012-11-22 15:47
标题: 从一百个数中找不存在的数
碰到个面试题目，有一百个1到100的数字，为乱序的，其中缺一个数字，简述用什么方法能够最快速的查找出缺的那个数字，以及循环多少次？大家有什么好的解法？
作者: hellioncu    时间: 2012-11-22 16:39
缺一个那就是99个了，5050-累加值即可
作者: 你还未够水准呢    时间: 2012-11-22 16:42
楼主的意思是有一个重复的

回复 2# hellioncu


   
作者: lxyscls_cu    时间: 2012-11-22 16:55
建个索引数组——1-100，初始为{0}

录入：有索引数组对应位置就+1

再轮一遍索引数组，哪个为0就缺哪个

2N{:3_189:}
作者: InMySin    时间: 2012-11-22 17:04
这个题目应该出现过了，使用异或运算应该是最快的方法了，加法也可以，但是加法应该比不上逻辑运算的速度。。
（另外我也想求求关于现代CPU执行 加法的需要多少时钟周期， 逻辑异或需要多少时钟周期 ？ 的干货 ）

首先得到 1-100 这些数字异或后得到的数字 Y= 1^2^..^100，使用循环99次得到.
然后用着Y 去异或那个99个数的数字， 最后Y里保存的就是缺失了的数字。 也是99次循环。

其实是同学提到的，他搞ACM，我很菜。。
原理：
Y = a^b^c;

e = Y ^ a ^ c = a^b^c^a^c = a^a^b^c^c = 0 ^ b ^ 0 = b .. 就是缺少了的b，异或运算的性质应该没记错。
有错请指出下，谢谢
作者: InMySin    时间: 2012-11-22 17:08
回复 5# InMySin

察，看错题目了， 100个 1-100的数字，其中缺少一个1-100中的数，那肯定有重复了。。这种解法就应该不正确了.

   
作者: folklore    时间: 2012-11-22 17:56
不计代价，最快

  2. int arr[100];  //< input


  5. int *pIn=arr-1;
  6. int sig100=0;
  7. int sigdes=0;
  8. int flag[101]={0};
  9. for(int i=1;i<=100;i++){
  10.    sig100|=i;
  11.    if(flag[pIn[i]]==0）｛
  12.       flag[pIn[i]]=1;
  13.       sigdes|=pIn[i];
  14.    ｝
  15. }
  16. return sigdes|sig100;
复制代码
作者: Sevk    时间: 2012-11-22 18:58
提示: 作者被禁止或删除 内容自动屏蔽
作者: __slucx__    时间: 2012-11-23 09:53
先用异或求重复数，
然后序列求和和5050比较，
少几就是重复数加几，
反之减
作者: pandaiam    时间: 2012-11-23 10:55
我能想到的和4楼一样...
作者: zhujiang73    时间: 2012-11-23 11:05
回复 4# lxyscls_cu


    通俗易懂，简单直接，好。 {:3_189:}
作者: conn2011    时间: 2012-11-23 16:22
回复 4# lxyscls_cu


    建个索引数组——1-100，初始为{0}
    声明变量 int sum = 0

    录入：
     if 索引数组对应位置的值为0 : 索引数组对应位置的值=1 且 sum +=  索引数组对应位置 (将所有非重复值累加)
   
   得出缺失数: 5050-sum
            

   
作者: cttnbcj    时间: 2012-11-26 09:52
BITMAP啊 ~~
作者: shang2010    时间: 2012-11-26 10:10
循环一次，但做两个逻辑
1重复检测，2累加

当然循环两次也是OK的
作者: sothicor    时间: 2012-11-26 13:40
题目的意思我理解了有点歧义，是100个数字里 拿走一个，还剩99个数，求出缺的那个数，还是说100个数里，有1个唯一重复的数字。
前者的话，用异或能解决，后一个再想想。。
  1. #include<stdio.h>

  3. int get_miss_no(int *data, int n);

  5. int main(void)
  6. {
  7.     int arr[4] = {5,2,1,3}; //假设5个数字中随机扣掉1个，还剩4个
  8.     printf("\nmiss no is %d\n", get_miss_no(arr,4));   
  9.     return 0;
  10. }

  12. int get_miss_no(int *arr, int n)
  13. {
  14.     int miss_no = arr[0];
  15.     for(int i = 1; i < n; i++)
  16.                 miss_no ^= arr[i];
  17.     for(int i = 0; i < n+1; i++)
  18.         miss_no ^= i+1;
  19.     return miss_no;
  20. }
复制代码
作者: leejqy    时间: 2012-11-26 13:43
方法：
1.【时空复杂度O(nlogn)】排序+扫描，找出重复的那个【挨在一块】，即可求出缺失的；
2.【时空复杂度O(n)】申请数组flag[100]，初始化为0，扫描数组，将相应的flag + 1,如果变成2，说明该值重复，从而可以得到缺失的；
3.【时间复杂度O(n),空间复杂度O(1)】
扫描一次，求得和S1, 和平方和S2：
设缺失的数为X, 重复的为Y；则有方程：
Y - X = S1 - (1+2+3....+100);
Y^2 - X ^2 = S2 - (1^2+2^2+....+100^);
即可求得X，Y
回复 1# rdcwayx


   
作者: crazyhadoop    时间: 2012-11-26 23:34
2L正解
作者: cokeboL    时间: 2013-01-06 16:44
回复 7# folklore


    这个要用 ^ 吧？
作者: liyapeng90    时间: 2013-01-06 18:26
貌似可以用集合的概念，就是标准模版库里面的
作者: vim_dev    时间: 2013-01-06 18:47
回复 5# InMySin

其实本质是异或的逆运算是异或自己吧，
比如c = a^b;    b = c^a; 也就是 a^b^a = b, 一个数异或另一个数两次其值不变。
   
作者: sqfasd    时间: 2013-01-06 19:00
假设重复的是X，缺的是Y，假设数组为a1,a2....a100,和为S
X-Y = S - 5050
X^Y = (1^2^...^100)^(a1^...^a100)
再遍历一遍，可解上面两个方程式
空间O(1), 时间O(N)



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