1에서 N 사이의 숫자 배열에서 번호가 누락되었습니다. 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에서만 발생합니다.