從一百個(gè)數(shù)中找不存在的數(shù)

發(fā)仔很忙

碰到個(gè)面試題目，有一百個(gè)1到100的數(shù)字，為亂序的，其中缺一個(gè)數(shù)字，簡述用什么方法能夠最快速的查找出缺的那個(gè)數(shù)字，以及循環(huán)多少次？大家有什么好的解法？

hellioncu

缺一個(gè)那就是99個(gè)了，5050-累加值即可

你還未夠水準(zhǔn)呢

樓主的意思是有一個(gè)重復(fù)的

回復(fù) 2# hellioncu


   

lxyscls_cu

建個(gè)索引數(shù)組——1-100，初始為{0}

錄入：有索引數(shù)組對應(yīng)位置就+1

再輪一遍索引數(shù)組，哪個(gè)為0就缺哪個(gè)

2N{:3_189:}

InMySin

這個(gè)題目應(yīng)該出現(xiàn)過了，使用異或運(yùn)算應(yīng)該是最快的方法了，加法也可以，但是加法應(yīng)該比不上邏輯運(yùn)算的速度。。
（另外我也想求求關(guān)于現(xiàn)代CPU執(zhí)行 加法的需要多少時(shí)鐘周期， 邏輯異或需要多少時(shí)鐘周期 ？ 的干貨 ）

首先得到 1-100 這些數(shù)字異或后得到的數(shù)字 Y= 1^2^..^100，使用循環(huán)99次得到.
然后用著Y 去異或那個(gè)99個(gè)數(shù)的數(shù)字， 最后Y里保存的就是缺失了的數(shù)字。 也是99次循環(huán)。

其實(shí)是同學(xué)提到的，他搞ACM，我很菜。。
原理：
Y = a^b^c;

e = Y ^ a ^ c = a^b^c^a^c = a^a^b^c^c = 0 ^ b ^ 0 = b .. 就是缺少了的b，異或運(yùn)算的性質(zhì)應(yīng)該沒記錯(cuò)。
有錯(cuò)請指出下，謝謝

InMySin

回復(fù) 5# InMySin

察，看錯(cuò)題目了， 100個(gè) 1-100的數(shù)字，其中缺少一個(gè)1-100中的數(shù)，那肯定有重復(fù)了。。這種解法就應(yīng)該不正確了.

   

folklore

不計(jì)代價(jià)，最快

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;
    

復(fù)制代碼

__slucx__

先用異或求重復(fù)數(shù)，
然后序列求和和5050比較，
少幾就是重復(fù)數(shù)加幾，
反之減

pandaiam

我能想到的和4樓一樣...