O(n) 시간과 O(1) 공간에서 0부터 n-1까지의 숫자 배열에서 중복 항목을 어떻게 찾을 수 있습니까?

O(n) 시간과 O(1) 공간에서 중복 찾기: 심층 설명

제기된 문제는 중복을 식별하는 것과 관련됩니다 0부터 n-1까지의 숫자를 포함하는 배열 내의 요소입니다. 문제는 O(n) 시간 복잡도 내에서 일정한(O(1)) 메모리 공간만 사용하여 이를 효율적으로 달성하는 것입니다.

제시된 솔루션은 해시 테이블이나 기타 추가 데이터가 필요하지 않은 독창적인 기술을 사용합니다. 구조. 대신 배열 자체의 값을 활용하여 중복 요소를 식별하고 표시합니다.

1. 배열 치환:

   내부 루프 치환 다음 논리에 기반한 배열:

   while A[A[i]] != A[i]
       swap(A[i], A[A[i]])
   end while

   이 순열 단계는 요소 x가 배열에 존재하는 경우 해당 인스턴스 중 하나 이상이 A[x]에 위치하게 됩니다. 이는 후속 단계에서 매우 중요합니다.

2. 중복 식별:

   외부 루프는 각 요소 A[i]를 검사합니다.

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

   A[i] != i이면 i가 올바른 위치에 없다는 의미입니다. 배열에서. 따라서 중복된 요소이므로 인쇄됩니다.

3. 시간 복잡도 분석:

   기법은 O(n) 시간에 실행됩니다. . 중첩 루프에는 n번 반복하는 외부 루프와 최대 n - 1번 반복을 수행하는 내부 루프가 있습니다(왜냐하면 각 스왑은 하나의 요소를 올바른 위치에 더 가깝게 가져오기 때문입니다). 따라서 총 반복 횟수는 n*(n - 1)로 제한되며 이는 O(n^2)이지만 n*(n - 1) = n^2 - n과 같이 O(n)으로 단순화할 수 있습니다. = n(n - 1) = n*n - n < n*n = O(n^2) = O(n).

4. 공간 복잡도 분석:

   알고리즘은 상수 공간만 사용합니다. , 입력 크기와 무관합니다. 중요한 통찰력은 순열에 활용되는 공간이 입력 배열 내에 이미 존재한다는 것입니다. 추가 저장 구조는 필요하지 않습니다.

5. 추가 참고 사항:

   • 알고리즘은 배열에 0부터 n까지의 정수가 포함되어 있다고 가정합니다. 1.
   • 시간 복잡도는 다음과 같은 경우에도 동일하게 유지됩니다.
   • 이 알고리즘은 중소 규모 배열에 효율적입니다. 대규모 배열의 경우 해시 테이블과 같은 데이터 구조를 사용하는 대체 접근 방식이 더 적합할 수 있습니다.

위 내용은 O(n) 시간과 O(1) 공간에서 0부터 n-1까지의 숫자 배열에서 중복 항목을 어떻게 찾을 수 있습니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!