데이터 구조를 사용하지 않고 두 세트의 교차를 찾는 알고리즘

Question

해시 테이블과 같은 외부 데이터 구조를 사용하지 않고 동일 요소의 두 배열 (예 : 정수)의 교차를 결정하는 알고리즘을 알고 싶습니다 (O (nlogn))?

Answer 1

정렬은, 각 소자 배열 반복기를 사용하여 반복 :

if A[iter1] > B[iter2]: increase iter2 
else if A[iter1] < B[iter2]: increase iter1 
else: element is in intersection, print and increase both iters 

정렬은 O(nlogn)이다 순회는 O(nlogn)

Answer 2

• 놓아이를 통해 배열
• 루프 전체 O(n)이고 상점 매치

뭔가 같은 ... N의

var A = [0...N]; 
var B = [0...N]; 
var result = []; 
Array.sort(A); 
Array.Sort(B); 
for(var x=0, y=0; x < N && y < N; x++) { 
    while(A[x] < B[y] && y < N) { 
     y++; 
    } 
    if(A[x] == B[y]) { 
     result.push(B[y++]); 
    } 
} 

Answer 3

사거리는 다양한 크기의 정수

을 감안할 때 n 개의 세트를 설정합니다. 각 세트에는 중복도 포함될 수 있습니다. 모든 세트의 교차점을 찾는 방법. 요소가 모든 세트에 여러 번 나타나면 결과에 여러 번 추가해야합니다.

예를 들어 {1,2,2,3,4} {2,2,3,5,6} {1,3,2,2,6}의 세 세트가 있다고 가정합니다. 주어진 집합의 교집합은 {2,2,3}이어야합니다.

다음은이 문제를 해결하는 효율적인 방법입니다.

1. 모든 세트를 정렬하십시오.
2. 가장 작은 세트를 가져와 모든 요소와 해당 빈도를지도에 삽입합니다.
3. 지도의 각 요소에 대해 다음을 수행하십시오. ... ..a. 요소가 세트에 없으면 무시하십시오. ... ..b. 각 집합에서 요소의 빈도를 찾습니다 (이진 검색 사용). 지도의 주파수보다 작 으면 주파수를 업데이트하십시오. ... ..c. 요소가 모든 세트에서 발견되면 결과에 추가하십시오.

시간 복잡도 : 'n'목록이 있고 목록의 평균 크기는 'm'이어야합니다. 정렬 단계는 O (n * m * log m) 시간 (평균 길이 m 인 n 개의 목록 정렬)을 필요로합니다. 탐색 단계는 O (m * n * log m) 시간이 걸린다. (목록의 각 요소에 대해 로그 m 시간으로 n 개의 목록을 검색합니다). 따라서 전체 시간 복잡도는 O (n m log m)입니다.

보조 공간 :지도를 저장하기위한 공간 (O (m)).