从一百个数中找不存在的数

发仔很忙

碰到个面试题目，有一百个1到100的数字，为乱序的，其中缺一个数字，简述用什么方法能够最快速的查找出缺的那个数字，以及循环多少次？大家有什么好的解法？

hellioncu

缺一个那就是99个了，5050-累加值即可

你还未够水准呢

楼主的意思是有一个重复的

回复 2# hellioncu


   

lxyscls_cu

建个索引数组——1-100，初始为{0}

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

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

2N{:3_189:}

InMySin

这个题目应该出现过了，使用异或运算应该是最快的方法了，加法也可以，但是加法应该比不上逻辑运算的速度。。
（另外我也想求求关于现代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

回复 5# InMySin

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

   

folklore

不计代价，最快

1. 
   
2. int arr[100];  //< input
   
3. 
   
4. 
   
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;
    

复制代码

__slucx__

先用异或求重复数，
然后序列求和和5050比较，
少几就是重复数加几，
反之减

pandaiam

我能想到的和4楼一样...