O（n）算法，找到缺失的整數

數組A包含範圍[0，n-1]中的n-1個唯一整數，即此範圍內有一個不在A中的數字。一個O（n）算法找到這個數字。除陣列A本身外，只允許使用O（1）個附加空間。O（n）算法，找到缺失的整數

需要一些幫助，對於這個問題，

2012-09-05 user1049336

作業的問題？ – woz

possib le重複[什麼是最優方法來計算列表中的哪個整數丟失？]（http://stackoverflow.com/questions/8967070/whats-the-optimal-way-to-calculate-which-integer-in- a-list-is-missing） –

總和的陣列。
計算expected sum using arithmetic progression formula

。這些數值：一個是0 + 1 + 2 + ... + n-1，另一種是你的實際元素的總和 - 認爲他們彼此有什麼不同，有什麼做一個有其他沒有。確保你知道它，而答案是微不足道的。

編輯：（理論評論）：
注意sum(array)需要2*log_2(max(arr))位。所以，如果你的元素都是32位整數，你將需要最多64位來表示總和。
從純粹的理論方法 - 它不是O(1)。但是，您可以使用數組本身（它包含多於2*log_2(max(arr))位）來存儲總和。

來源

2012-09-05 13:45:06 amit

awww，來吧，爲什麼你馬上給出正確答案，這很容易，讓OP爲他/她自己想一下;） – codeling

@nyarlathotep：建議採取，我編輯答案更加暗示然後回答。 – amit

是的，很好編輯：D。可能是作業畢竟，我們不想讓這太容易;） – codeling

使用附加tmp變量與-1初始化，然後種排序陣列中代替使用作爲tmp位置n：

function find_missing(array) 
begin 
    tmp := -1 
    i := 0; 
    while i<length(array) 
    if (array[i] = -1) or (array[i] = i) then 
     // either on a cell with the right number or 
     // a candiate for the missing number, just go on 
     i := i + 1 
    else if array[i] = n then 
     // use tmp as the nth cell 
     array[i]=tmp 
     tmp=n 
    else 
     // swap the value of the current cell with the value 
     // of the cell were the value i should be 
     swap(array, i, array[i]) 
    end if 
    end while 
end

-1應指向丟失的數量。

來源

2012-09-05 14:53:55 Kwariz

這裏不用另一種方法：

設定爲0
一個臨時變量號對於在陣列中的每個元素中，設置總數=編號XOR元件
對於每個編號M，M> N和M < 2 **（小區（LOG2（N））中設置總數=編號XOR中號
缺失數是數

來源

2012-09-06 17:10:32 gusbro

O（n）算法，找到缺失的整數

回答

相關問題