問題： 某數(shù)組A[1..n]含有所有從0..n的所有整數(shù)，但其中有一個整數(shù)不在數(shù)組中，通過利用一個輔助數(shù)組B[0..n]來記錄A中出現(xiàn)的整數(shù)，很容易在O(n)時間內(nèi)找出所缺的整數(shù)。但在這個問題中，我們卻不能由一個單一操作來訪問A中的一個完整整數(shù)，因為A中元素是以二進制表示的。我們所能用的唯一操作就是“取A[i]的第j位”這個操作所花時間為常數(shù)。 證明：如果訪問數(shù)組A中信息的唯一方式是這種單一位操作，仍能在O(n)時間內(nèi)找出所缺的整數(shù)。A之外的任一完整整數(shù)仍然可以由一個單一操作來訪問。【算法導論 中文版 P50 4-2】
昨天晚上看算法導論看到了這一題，沒有想多久，沒想通。當時想的是把A中的每一個信息都逐個獲取，但是復雜度是O(lgn)，今天在網(wǎng)上看別人的博客，學會了這個方法。利用了二進制的特點。(后面的東西是修改了Jianxing的blog里的。地址http://gonewiththedream.spaces.live.com/blog/cns!4327B97AC534D77E!235.entry)
基本方法就是用二分法：
1, 遍歷整數(shù)0到n的第一位，分成兩個數(shù)組：P1[1] 和P0[1]，分別代表第一位是1，0的數(shù)，并記錄第一位是1的個數(shù)CountN，代價為O(n)
2, 遍歷數(shù)組A[1...n]的第一位, 分成兩個組：Q1[1]和Q0[1]，分別代表第一位是1，0的數(shù)，并記錄1的個數(shù)CountA，代價為O(n)
3, 比較CountN和CountA的值，結(jié)果可能有兩種情況CountN = CountA，或者CountN = CountA + 1， 前者表明所缺數(shù)的第一位為0， 后者為1，代價為O(1)
4, 通過3的結(jié)果，隨后我們可以在P1[1]和Q1[1]（CountN>CountA，即缺少第一位為1的數(shù)） 或者 P0[1]和Q0[1](CountN=CountA，即缺少第一位為0的數(shù))中的第2位中重復步驟1，2中的操作，記錄數(shù)組P1[2]、P0[2]和CountN'及Q1[2]、Q0[2]和CountA'。代價為O(n/2)和O(n/2), 經(jīng)過比較后可得到所缺數(shù)第二位是0還是1，決定接下來比較P1[2]和Q1[2] 或者 P0[2]和Q0[2]，代價O(1)
5, 不斷重復Ceiling(lg(n))次，最后即可找到所缺數(shù)總代價為2* (O(n) + O(n/2) + ... +O(n/pow(2, k))) + ... + O(1)) = 2* O(2n) = 4*O(n) = O(n)
當然這里忽略了一個問題，如果A中缺了一個，這應該是n-1個數(shù)，則多出來的那個數(shù)是什么呢，如果和其他數(shù)有重復，上面的方法就無效了，情況變得相當復雜。因此上面的只適用于多出的一個數(shù)為0，或者干脆就只有n-1個數(shù)。