Disjoint set using Search and Sorting

Question

У меня вопрос в классе алгоритмов, и я не могу его решить. В вопросе говорится, что Theres является алгоритмом сортировки с O(nlogn), а поиск выполняется путем поиска двоичного поиска O(log n). Два набора дают P & Q, и я должен разработать алгоритм для определения того, являются ли два набора непересекающимися.

Answer 1

O(N) решение (при условии, что два набора сортируются):

1. слияния двух отсортированных наборов информации как элемент принадлежит к которому устанавливается
2. траверс через список слияния, если вы найти два равных элемента из двух наборов, чем непересекающиеся, если они достигают до конца, чем disjoint

например. не

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

слилась набор =

элементы:1 2 4 4 6 7

установить нет (а/б):1 2 1 2 1 2

Теперь мы ясно видим, что две четверки являются последовательными и оба из двух разных наборов, следовательно, не пересекаются.

EDIT:

Если ваша потребность найти множество не пересекается или не чем простое слияние даст вам это. Как только вы обнаружите, что оба элемента в наборах равны, чем просто возврат, говорящий не дизъюнктным другим, если они могут достигать до конца как непересекающихся.

Вопрос, связанный с контейнером. Ниже, что:

class Element{ 
int i; 
int setInfo 
} 

Теперь объявить массив как: Element[] e=new Element[X];

Надежда я ясно.

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.