배열에서 하나의 비 반복 요소를 찾으시겠습니까?

Question

하나의 요소 만 반복되지 않으면 n 요소의 배열을 가지며, 다른 모든 숫자는> 1 번 반복됩니다. 그리고 배열의 숫자 범위에는 제한이 없습니다.

일부 솔루션은 다음과 같습니다 요소를 찾아 다음

• 해시,의 사용을 제작하지만 머지 소트 O(nlogn) 사용하여 목록 정렬 선형 시간 복잡도하지만 매우 빈약 한 공간의 복잡성
• 초래하고 반복하지 않음

더 좋은 해결책이 있습니까?

Answer 1

하나의 일반적인 접근법은 요소를 ID (인덱스)를 사용하여 다른 "버킷"에 배포 한 다음 가장 작은 크기 (1 in)의 버킷을 찾는 버킷 화 기술 (해싱은 그러한 기술 임)을 구현하는 것입니다. 너의 경우). 이 문제는 소수 민족 요소 문제라고도합니다. 세트에 고유 한 요소가있는만큼 많은 양동이가 있습니다.

해시로이를 수행하는 것은 충돌 및 알고리즘이이를 처리하는 방법 때문에 문제가됩니다. tries 및 extendable hashing과 같은 특정 연관 배열 접근법은 문자열에 더 적합하므로 적용되지 않는 것처럼 보입니다.

위의 응용 프로그램 중 하나는 Union-Find data structure입니다. 당신의 세트는 버킷이 될 것이고 호출 당 $ O (\ alpha (n)) $의 비용으로 배열의 각 요소에 대해 MakeSet()과 Find()를 호출해야 할 것입니다. $ \ alpha (n) $는 매우 느리게 성장하는 inverse Ackermann 함수입니다. 당신은 그것을 사실상 일정하다고 생각할 수 있습니다.

요소가 이미 존재하면 Union을 수행해야합니다. 최소 카디널리티로 세트를 추적하기 위해 몇 가지 변경 사항을 적용하면이 솔루션이 작동합니다. 이 솔루션의 시간 복잡도는 $ O (n \ alpha (n)) $입니다.

또한이 문제는 Element Uniqueness problem과 약간 관련이있는 것으로 보입니다.

Answer 2

엄격한 공간 제한이있는 경우 다중 패스 검색을 시도하십시오.

입력에 n 개의 요소가 있고 메모리에 m 개의 요소 만 저장할 수 있다고 가정 해보십시오. 해시 테이블 접근법을 사용하는 경우, 최악의 경우 n/2 개의 고유 번호를 처리해야 m> n/2가됩니다. 만약 당신이 큰 m을 가지고 있지 않다면, k = (max (input) -min (input))/(2m) 그룹으로 n 개의 원소를 나눌 수 있고, n 개의 입력 원소를 k 번 스캔 할 수있다. case) :

첫 번째 실행 : 값이 < 분 (입력) + m * 2 인 모든 요소를 ​​해시 가져 오기/표시/표시 만합니다. 범위 (min (input), min (input) + m * 2)에서 최대 m 개의 고유 요소가 있으므로이를 처리 할 수 ​​있기 때문입니다. 운이 좋으면 이미 고유 한 것을 찾은 다음 계속 진행하십시오.

2 실행 : 만 범위 내의 값을 갖는 요소를 작동 (분 (입력) + m의 * 2 분 (입력) + m * 4) 등, 등 이와

, 당신은 O (KN)에 시간 복잡도를 손상하지만 아이디어는 내 마음에 와서

Answer 3

두 당신은 O (m)의 경계 공간의 복잡성을 얻을 :

• smoothsort보다 더 나은 대안이 될 수 있습니다 당신의 필요에 따라 인용 된 mergesort는 메모리 사용량에서 O (1), 최악의 경우 O (nlogn) e는 병합 정렬이지만 O (n)은 최상의 경우입니다. splay tree의 (반전) 아이디어를 바탕으로

  는

• , 당신은 그들이 (스플레이 트리로 대신 위의) 사용되면 아래쪽으로 잎을 밀어 것 나무의 종류를 만들 수 있습니다. 이것은 여전히 ​​당신에게 종류의 O (nlogn) 임플란트를 줄 것이지만, 장점은 유일한 요소를 찾는 O (1) 단계 일 것입니다, 그것은 루트가 될 것입니다. 소트 알고리즘은 O (nlogn) + O (N)의 합이며,이 알고리즘은 O (nlogn) 될 + O (1)

그렇지 않으면 (해시 기반 솔루션을 이용하여 설명한 바와 같이 추천 해시로 구현 된 집합)은 O (n) 알고리즘 (O (n))을 사용하여 계산 참조를 삽입하고 O (n)을 사용하여 고유 요소를 찾도록 설정합니다.)하지만 메모리를 싫어하는 것 같았습니다 사용법, 이유는 모르겠지만. 메모리가 저렴합니다. 요즘 ...