이것은 잠시 전에 만났던 흥미로운 질문으로 문제를 해결하는 데 도움이되었습니다.크기 n 배열에 누락 된 정수 m
그것을 누락 M 정수와 숫자 1,2 .., N + M 로 저장된 사이즈 N의 정렬되지 않은 정수 배열이있다. M 및 N은 이미 알려져있다. 가장 효율적인 방법으로 누락 된 M 정수를 찾는 알고리즘을 작성하십시오. ,
인덱스 번째 I 값 I에게 가진 요소를 함유하도록 크기 N + M 배열로 매핑 그것을 시도했지만, 이것은 2 스캔 (매핑 1 필요 1 M 누락 된 번호 찾기).
내가 만난 책에서 단일 스캔 솔루션이 가능하지만 도착하지 못했습니다. 이 문제를 해결하는 방법에 대한 아이디어가 있습니까?
배열 상단에 매핑 된 이중 연결 목록을 사용하여이 작업을 수행 할 수 있습니다. 링크 된리스트에서 그 위치를 제거 (스킵)에 대한 연결 목록을 각각 입력 된 숫자에 대응하는 위치 업데이트에 입력하면 인덱스를 통해 패스
position 1 2 3 4 5 6 ...
next 2 3 4 5 6 7 ...
prev 0 1 2 3 4 5 ...
하지만 누락 된 정수를 출력하기 위해 연결된 목록을 반복 할 필요가 없습니까? 내가 이해할 때'> 1' 루프인가? – irrelephant
@irrelephant 당신이 그것을 인쇄하고 싶다고 가정하면 내기를 걸 수 있습니다. 나는'O (N) + O (M)'의 시간 복잡성 관점에서 더 잘할 수 있다고 생각하지 않는다.'N '의 끝에 도달 할 때까지'M '. 이미 인쇄를 시작했다면,'N'의 마지막은 여러분이 이미 인쇄 한 것을 담아 출력물을 망칠 수 있습니다. M : N << 위의 주석에 링크 된 [오히려 인상적인 수학적 답변] (http://stackoverflow.com/a/3492967/1756702)과 같이 공간 복잡성 관점에서 더 잘 할 수 있다고 확신합니다. 하는 것처럼 보입니다. –
Big-O 표기법을 사용해서는 안됩니다. 나는'M '을 인쇄하고 싶다면'N '과'M '을 한 번 통과하는 것보다 더 잘 할 수 없다고 생각한다고 말하고자합니다. –
하나의 스캔 알 고를 적어주세요. 감사. –
이 질문은 매우 현지화 된 것으로 보이며 문제를 직접 해결하려고 시도했음을 증명하지 못했습니다. – lockstock
@lockstock 죄송합니다. 나는 그 질문을 편집했다. 희망이 도움이됩니다. – sanz