최적의 시간 및 공간 복잡도를 갖는 배열에서 중복 항목을 찾는 방법은 무엇입니까?

최적의 시간과 공간 복잡도로 중복 요소 찾기

소개:
중복 요소 검색 작업 배열은 프로그래밍에서 흔히 발생하는 문제입니다. 해시 테이블과 같은 보조 데이터 구조를 사용하는 솔루션은 단순성을 제공하지만 공간 효율성을 저하시킵니다. 이 기사에서는 일정한 공간 소비 O(1)을 유지하면서 선형 시간 O(n)에서 중복을 식별하는 독창적인 알고리즘을 제시합니다.

문제 설명:
주어진 배열 0부터 n-1까지의 n 요소(일부 숫자는 여러 번 나타날 수 있음) 중에서 배열에서 중복 요소를 찾습니다.

최적 알고리즘:

// Iterate through the array
for i = 0 to n - 1:
    // Swap elements until A[A[i]] = A[i]
    while A[A[i]] != A[i]:
        swap(A[i], A[A[i]])
    end while

// Identify duplicates based on A[i] != i
for i = 0 to n - 1:
    if A[i] != i:
        print A[i]
    end if
end for

통찰력:
알고리즘은 배열의 각 요소가 이상적으로는 해당 인덱스에 있어야 한다는 사실을 활용합니다. 배열의 요소를 사용하여 순열을 생성하여 존재하는 요소가 올바른 인덱스에 매핑되도록 합니다. 첫 번째 루프는 배열을 반복하고 각 요소가 스왑을 통해 의도한 인덱스에 도달하는지 확인합니다.

설명:
첫 번째 루프는 모든 요소 x에 대해 다음과 같은 조건이 충족되도록 배열을 순열합니다. 적어도 한 번 이상 나타나면 하나의 인스턴스가 인덱스 A[x]에 있습니다. 각 스왑에서 잘못된 요소에 해당하는 항목이 수정되어 총 스왑 수가 요소 수 N-1로 제한되도록 보장합니다.

두 번째 루프는 각 요소의 인덱스를 인쇄하여 중복을 식별합니다. 인덱스와 일치하지 않는 요소는 원래 배열에 없음을 나타냅니다.

결론:
이 알고리즘은 입력 배열을 영리하게 사용하여 배열에서 중복 요소를 효율적으로 식별합니다. 그 자체. O(n) 시간과 O(1) 공간 복잡성으로 인해 광범위한 실제 애플리케이션에 적합합니다.

위 내용은 최적의 시간 및 공간 복잡도를 갖는 배열에서 중복 항목을 찾는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!