O(n) 시간과 O(1) 공간을 사용하여 배열에서 중복 항목을 찾는 방법은 무엇입니까?

O(n) 시간과 O(1) 공간에서 중복을 찾는 효율적인 알고리즘

이 프로그래밍 챌린지에서 우리는 효율적인 알고리즘을 추구합니다. 가능한 반복을 통해 0에서 n-1까지의 정수 배열에서 중복 요소를 식별하고 인쇄하는 알고리즘입니다. 이 과제에는 O(n) 시간 복잡도 내에서 작동하고 일정한 메모리 공간만 소비하는 알고리즘이 필요합니다.

이 문제에 대한 효과적인 접근 방식 중 하나는 "배열 수정" 기술입니다. 알고리즘은 다음과 같이 작동합니다.

1. 첫 번째 루프:

   • 다음과 같이 표시되는 배열의 각 요소를 반복하는 루프를 초기화합니다. A[i].
   • 각 A[i]에 대해 A[A[i]]가 A[i]와 같은지 확인합니다.
   • 그렇지 않은 경우 A[i]를 A[로 바꿉니다. A[i]].

2. 두 번째 루프:

   • 루프를 재설정하여 각 A[i]를 반복합니다.
   • i와 같지 않은 A[i]에 대해 A[i]를 인쇄합니다. 이 단계에서는 중복되지 않은 요소가 i와 동일한 A[A[i]]를 갖기 때문에 중복된 요소를 식별합니다(즉, 올바른 위치에 있음).

이 알고리즘은 첫 번째 루프에서 각 요소를 최대 한 번 확인하고 수정하므로 O(n) 시간에 작동합니다. 게다가 추가적인 데이터 구조를 사용하지 않기 때문에 O(1) 공간만 활용합니다.

예를 들어 입력 배열 {1, 2, 3, 1, 3, 0, 6}을 생각해 보세요. 알고리즘을 실행한 후 배열은 다음과 같이 수정됩니다.

[1, 2, 3, 1, 3, 0, 0]

두 번째 루프는 중복된 요소 1과 3을 인쇄합니다.

위 내용은 O(n) 시간과 O(1) 공간을 사용하여 배열에서 중복 항목을 찾는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!