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

O(n) 시간과 O(1) 공간에서 중복 찾기

0에서 n까지의 숫자를 포함하는 n 요소의 배열이 주어졌습니다. -1, 일부 숫자가 여러 번 나타날 수 있는 경우 목표는 O(n) 시간 내에 일정한 메모리 공간을 사용하여 중복 요소를 찾는 것입니다.

이를 달성하기 위해 다음과 같은 흥미로운 접근 방식을 활용할 수 있습니다. 해시 테이블과 같은 추가 데이터 구조가 필요하지 않습니다.

제안된 알고리즘은 다음과 같이 작동합니다.

1. 순열 루프:

   • i에 대한 배열을 0에서 n-1까지 반복합니다.
   • 이 루프 내에서 A[A[i]]가 A[i]와 같아질 때까지 다음 단계를 수행합니다. 이는 A[i] 요소가 올바른 위치에 있음을 의미합니다.
   • A[i]를 A[A[i]]로 바꿉니다. 이렇게 하면 요소 A[i]가 올바른 위치에 한 단계 더 가까워집니다.

2. 중복 식별 루프:

   • i부터 n-1까지 한 번 더 배열을 반복합니다.
   • A[i]가 i와 같지 않으면 인덱스 A[i]에 i의 중복이 있음을 의미합니다.
   • A[i]를 중복으로 인쇄합니다.

이 알고리즘은 모든 중복 요소가 식별되도록 보장합니다. 외부 루프는 n번 실행되고, 내부 루프는 최대 n-1번 실행됩니다. 따라서 알고리즘은 O(n) 시간에 실행됩니다. 추가 데이터 구조를 사용하지 않습니다. 즉, O(1) 공간에서 작동합니다.

제공된 코드는 C에서 알고리즘 구현을 예시합니다.

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