1からNまでの数字の配列から欠けている番号

Question

あなたは、サイズがKの配列が1..Nの間に入っていて、この配列から欠けている1からNの間のすべての数字を出力します。 ソリューションは最高の複雑さで動作するはずです。

ありがとうございました。

Answer 1

for i := n - k + 1 to n 
    A[i] := A[1] 
end for 

for i := 1 to n - k 
    while A[A[i]] != A[i] 
     swap(A[i], A[A[i]]) 
    end while 
end for 

for i := 1 to n 
    if A[i] != i then 
     print i 
    end if 
end for 

コードはO（n）時間で実行されます。スワップはif A[i] != iのみ発生します。