값이 다른 정수 쌍의 수 찾기

Question

정수 배열을 가지고 있다면 O (n^2) 이외의 다른 효율적인 방법으로 어떤 정수가 다른 정수 쌍의 수를 찾을 수 있습니다. 주어진 가치? 예 : 배열 4,2,6,7의 경우 2로 다른 정수 쌍의 수는 2 {(2,4), (4,6)}입니다. 감사합니다. .

Answer 1

목록에서 세트를 만듭니다. 델타에 의해 모든 요소가 증가하는 다른 세트를 만듭니다. 두 세트를 교차시킵니다. 이 값은 쌍의 상위 값입니다. 파이썬

: 세트 작성

>>> s = [4,2,6,7] 
>>> d = 2 
>>> s0 = set(s) 
>>> sd = set(x+d for x in s0) 
>>> set((x-d, x) for x in (s0 & sd)) 
set([(2, 4), (4, 6)]) 

은 O (N)이다. 집합을 교차하는 것은 또한 O (n)이기 때문에 선형 시간 알고리즘입니다.

Answer 2

요소를 해시 테이블로 구현 된 다중 세트에 저장합니다. 그런 다음 각 요소 n에 대해 멀티 세트에서 발생 횟수를 확인하고 합산하십시오. n+2을 검사 할 필요가 없기 때문에 각 쌍을 두 번 계산하게됩니다.

평균 효율은 O (n)이고 최악의 경우 O (n * logn) 또는 O (n^2)입니다 (해시 테이블 구현에 따라 다름). 멀티 세트가 균형 잡힌 트리로 구현되는 경우 O (n * logn)가됩니다.

Answer 3

배열을 정렬 한 다음 두 개의 포인터로 스캔합니다. 첫 번째 점이 a을 가리킨다 고 가정하고, 두 번째 점을 찾을 때까지 두 번째 점을 앞으로 내리십시오 (a+2). 거기에 있다면 합계를 늘리십시오. 그런 다음 첫 번째 포인터를 증가시키고 반복하십시오. 각 단계에서 두 번째 포인터는 이전 단계에서 끝난 위치에서부터 시작됩니다.

배열에 중복이 허용되면 첫 번째 포인터를 증가 시키면 동일한 정수가 다시 발생하는 경우 두 번째 포인터가 겹쳐진 횟수를 기억해야합니다.

이것은 스캔이 선형 시간이므로 O(n log n) 최악의 경우 (정렬의 경우)입니다.

최악의 경우 고정 폭 정수에 대한 해시 테이블 기반 솔루션은 O (n)에서 기수 정렬을 사용하여 고정 너비 정수를 정렬 할 수 있기 때문에 예상 된 O (n) 시간이라고 말할 수 있습니다. 엔). 실제로 더 빠른 것은 또 다른 문제입니다. 해시 테이블은 빠르지 만 구현에 따라 많은 메모리 할당 (노드의 경우) 및/또는 잘못된 지역화 된 메모리 액세스가 포함될 수 있습니다.

Answer 4

원하는 차이가 0이고 배열의 모든 요소가 동일하다면 출력의 크기는 O (n²)이므로 모든 알고리즘의 최악의 경우는 반드시 O (n²)입니다. (다른 한편으로, 평균 또는 대소 문자를 구별하는 행동이 현저히 향상 될 수 있습니다.)

Answer 5

정렬 계산에서와 같이 배열의 숫자를 해시하기 만하면됩니다. 0을 색인하고 다른 하나는 색인 2 (또는 일반적으로 색인 d)를 가리 킵니다. 두 인덱스의 값이 0이 아닌지 확인한 다음 예인 경우 두 값 중 큰 값으로 카운터를 증가시키고 그렇지 않으면 쌍을 존재하지 않는 카운터를 변경하지 않습니다. 이제 두 인덱스를 증가시키고 두 번째 인덱스가 배열의 끝에 도달 할 때까지 계속하십시오. 카운터의 전체 값은 차이가있는 쌍의 수입니다 d. 시간 복잡도 : O (n) 공간 복잡성 : O (n)