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