검색 및 정렬을 사용하여 부 집합 집합

Question

내 알고리즘 클래스에서 질문이 있는데 해결할 수 없습니다. 질문에 Theres는 정렬 알고리즘이 O(nlogn)이고 이진 탐색은 O(log n)입니다. 두 세트는 P & Q이고 두 세트가 비 연속적인지 여부를 결정하는 알고리즘을 설계해야합니다.

Answer 1

O(N) 용액 (두 세트의 정렬 가정) 병합 목록을

이송을 설정할 수있는 요소가 속하는 같은

1. 는 경우, 정보는 두 개의 정렬 된 세트를 병합 끝까지 도달 할 수없는 경우 두 세트에서 두 개의 동일한 원소를 찾는다. 분리형

예 :

a= 1, 4, 6 
b= 2, 4, 7 

은 이제 =

요소를 설정 병합 된 :1 2 4 4 6 7

설정에는 (A/B) : 이제 1 2 1 2 1 2

우리가 명확하게 두 발로 연속 것을 볼 수 없다 둘 다 서로 다른 두 세트에서 나오므로 분리되지 않습니다.

편집 :

당신의 필요가 세트 간단한 병합 당신에게 그것을 줄 것보다 해체하거나하지 찾을 경우. 당신이 세트에서 두 원소를 찾자 마자 동등한 것이지, 둘 중 하나가 끝날 때까지 도달 할 수 없다면 다른 원소가 떨어져 있지 않다는 말로 귀가한다.

컨테이너 관련 질문. Element[] e=new Element[X];

희망 난 분명 이니로

이

class Element{ 
int i; 
int setInfo 
} 

이제 배열을 선언 : 아래는 점이다.

Answer 2

두 세트 사이에 공통 요소가없는 경우에만 두 세트가 연결되지 않습니다. 나는이 두 세트에 각각 n 개의 원소가 있다고 가정하고있다. 이 알고리즘은 nlog (n) 시간에 공통 요소를 확인합니다. 발견 된 공통 요소가 없으면 두 세트가 서로 떨어져 있음을 의미합니다.

For each element in set "P" search whether that number exist in set "Q". 
Time complexity - n*log(n) 
Log(n) to search in set Q and this search will be done "n" times.