題目：數(shù)組A中包含n-1個[0,n-1]內(nèi)的不同整數(shù)，n個數(shù)中只有一個數(shù)不在所給的數(shù)組中。設計一個找到這個數(shù)的O(n)時間的算法。除了數(shù)組A自身以外，只能利用O(1)的額外空間。

與之相似的另一個題目見《算法導論》思考題4-2：問題同上，但在這里，不能由一個單一操作來訪問A中的一個完整整數(shù)，因為A中整數(shù)是以二進制表示的。我們所能用的唯一操作就是“取A[i]的第j位”，這個操作所花時間為常數(shù)。題目要求：證明如果僅用此操作，仍能在O(n)時間內(nèi)找出所缺整數(shù)。

第一個題目可以想出以下幾種方法：

解法一：[0,n-1]這個區(qū)間中所有整數(shù)的和不變，為n*(n-1)/2，對數(shù)組A中的所有元素求和，設為s，則丟失的整數(shù)就是n*(n-1)/2 – s。

解法二：異或運算。異或是個非常神奇的運算。設所缺的整數(shù)為k，[0,n-1]區(qū)間中所有n個數(shù)的異或結(jié)果為s(n)，異或運算滿足交換率和結(jié)合率，所以s(n)可以被看作[0,n-1]中去掉k外的另外n-1個數(shù)的異或結(jié)果s(n-1)和k的異或。也即：s(n)=s(n-1)^k，我們給等式兩邊同時異或s(n-1)，等式變成了：s(n-1)^s(n)=s(n-1)^s(n-1)^k=k。而且，很明顯s(n-1)其實就是數(shù)組A中所有元素的異或。所以，解法二就是：求出[0,n-1]內(nèi)所有整數(shù)的異或結(jié)果s，再求出數(shù)組A中所有元素的異或結(jié)果t，所缺的整數(shù)就是s異或t。

解法三：因為A自身也有n-1個位置。可以把A作為一個散列表，這樣做雖然能夠得到結(jié)果，但是破壞了數(shù)組A。

至于《算法導論》思考題4-2的解法，在《算法藝術與信息學競賽》上有解答。思路簡述：自然數(shù)順序的二進制表示最低位總是0和1交替出現(xiàn)，所以，首先讀取數(shù)組A中所有元素的最低二進制位，如果得到的0和1的個數(shù)一樣多，則說明所缺整數(shù)的最低二進制位為0，否則，哪個少，所缺整數(shù)的最低二進制位就是哪個。比如，我們得到所缺整數(shù)的最低二進制位為0，那么，說明數(shù)組A中最低二進制位為1的那些整數(shù)已經(jīng)與此題無干，只需要在那些最低位為0的整數(shù)中找所缺整數(shù)。所以，時間復雜度是：T(n)=T(n/2)+n，計算：

對n的上取整或下取整不影響時間復雜度。即T(n)=O(n)。