查找數組中缺失的數字，時間複雜度爲O（N），空間複雜度爲O（1）

Question

給出一個包含n個唯一整數的數組0 < = x_i < 2 * n。 打印所有整數0 < = x < 2 * n不存在於此數組中。

實施例：

find_missing（[0]）= [1]

find_missing（[0，2，4]）= [1，3，5]＃因爲所有數值[0， 1，2，3，4，5]

find_missing（[]）= []

find_missing（[0，1，4，5]）= [2，3，6，7]＃因爲所有數字是[0,1,2,3,4,5,6,7]

怪癖是關於要求：

時間複雜度O（n） - 但是應該有一些固定的常數C獨立於輸入的大小，這樣陣列的每個元素都被寫入/讀取< C次，所以基數排序是不行的。 （1） - 你可以修改初始數組，但是sort（initial_array）必須等於sorted（array_after_executing_program）並且你不能在數組範圍外存儲整數[0,2n）（假設它是一個uint32_t數組）。

我看到了很多複雜的解決方案，但後來我發現這一點：

public void printNotInArr(int[] arr) { 
    if(arr == null) 
     return null; 

    int len = arr.length; 
    int max = 2 * len; 

    for(int i = 0; i < len; i++) { 
     System.out.println(max - arr[i] - 1); 
    } 
} 

我相信這是最好的解決辦法，但我不知道。我想知道爲什麼這是行不通的。

Answer 1

As @ LasseV.Karlsen指出，[0,3]是一個簡單的反例，說明該解決方案如何工作。然而，這是一個非常簡單的解決方案（使用Python）：

def show_missing(l): 
    n = len(l) 

    # put numbers less than n into the proper slot 
    for i in range(0,n): 
    while l[i]<n and l[i]!=i: 
     j = l[i] 
     l[i] = l[j] 
     l[j] = j 
    for i in range(0,n): 
    if l[i]!=i: 
     print('Missing %s'%i) 

    # put numbers greater than n into the proper slot 
    for i in range(0,n): 
    while l[i]>=n and l[i]!=i+n: 
     j = l[i] 
     l[i] = l[j-n] 
     l[j-n] = j 
    for i in range(0,n): 
    if l[i]!=i+n: 
     print('Missing %s'%(i+n)) 

這個想法很簡單。我們首先重新排列元素，使得每個小於n的值j都存儲在索引j處。然後我們可以通過這個數組，輕鬆地找出那些缺失的那個下面的那個。

然後，我們重新排列元素，使得每個大於或等於n的值j都存儲在索引j-n中。再次，我們可以通過數組輕鬆挑選出大於或等於n的缺失數。

由於只使用了幾個局部變量，O（1）空間複雜度得到了滿足。

由於嵌套循環，O（n）時間複雜度有點難以看清，但不難證明我們永遠不會交換超過n個元素，因爲一個新元素被放入其中每次交換的適當位置。

由於我們只交換了數組的元素，所有原始元素仍然在數組中的要求也得到了滿足。