누락 된 번호 찾기

Question

N (N < 10)까지의 모든 숫자 배열이있는 경우 누락 된 모든 숫자를 찾는 가장 좋은 방법은 무엇입니까? 예 : 전에서

N = 5 
1 5 3 2 3 

Output: 1 5 4 2 3 

는, 숫자 4는없는 일이었고, 2 3S가 있었다, 그래서 우리는 4 첫 번째 교체하고 이제 배열이 완료 - 5까지의 모든 숫자가 .

이 작업을 수행 할 수있는 간단한 알고리즘이 있습니까?

Answer 1

set data structure - N까지 모든 숫자에 대해 하나씩, 실제로 보았던 숫자에 대해 하나씩, 그리고 세트 차이점을 사용할 수 있습니다.

Answer 2

이 작업을 수행하는 한 가지 방법은 배열의 각 요소를 차례대로 살펴보고 이미 확인한 요소에 이전에 요소가 있는지 여부를 확인하는 것입니다. 그렇다면 이전에 보지 못했던 번호로 변경하고 계속하십시오.

친구를 소개해 드리겠습니다. Schlemiel the Painter. 더 효율적인 방법의 발견은 독자에게 어려운 과제로 남아 있습니다.

Answer 3

이런 종류의 숙제는 보이지 않는 경우 저희에게 알려주십시오. 나는 당신에게 작은 힌트를 줄 것이고, 이것이 숙제가 아니라고 확신한다면 나의 대답을 향상시킬 것이다.

내 팁은 이것입니다. 이것을 손으로 직접한다면 어떻게 할 수 있습니까? 몇 시간 동안 여분의 목록을 작성 하시겠습니까? 목록을 통해 몇 번 읽으시겠습니까?

간단한 문제의 경우 직관적 인 방법으로 알고리즘을 모델링하는 것이 효과적 일 수 있습니다.

Answer 4

은 (연관 배열로) 사이즈 N. output, used 2 개 배열을 유지 내지 1 ≤ X ≤ N.

내의 모든 숫자를 가정한다. 모두 0으로 초기화하십시오.

오른쪽에서에서 스캔하면 used이 아닌 한 output으로 채우십시오.

사용하지 않는 값을 확인한 다음 빈 슬롯 (제로)에 output 슬롯을 순서대로 넣습니다.

O (N) 시간 복잡도, O (N) 공간 복잡성.

Answer 5

N이 실제로 작기 때문에 number i가 k 번 나타나는 경우 F [i] = k를 사용할 수 있습니다. 이제

int F[10]; // make sure to initialize it to 0 
for (int i = 0; i < N; ++i) 
    ++F[ numbers[i] ]; 

는 중복을 대체 전화 번호 배열을 통과하고 현재 번호가 두 번 이상 나타나는 경우, 그 수를 감소하고 0 번 나타나는 숫자로 대체하고 그 숫자의 수를 증가합니다. 전혀 나타나지 않는 숫자의 목록을 보관하면이 O (N)을 유지할 수 있습니다. 숙제처럼 들리 겠지만 정확하게해야 할 일을 알아 보도록하겠습니다.

Answer 6

오늘 제가 읽은 링크가 도움이 될 것 같습니다. http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html