У меня есть x наборов с y элементами (unsorted integers) в каждом из них. Я хочу найти максимальный размер пересечения между парой этих множеств.
Например:
* 5 наборов, размер = 3
установить 1:1 2 3
установить 2: 4 2 3
установить 3: 5 6 7
установить 4: 5 8 9
установить 5: 5 10 11
максимальное пересечение установило 1 с множеством 2, а размер 2; ответ 2.
Итак, я могу сделать это в O (x ^ 2 * y), используя HashSets
, просто глядя на все пары и вычисляя их размер пересечения. Но я хочу сделать это быстрее. Я думаю, что есть определенный алгоритм или структура данных, которые могут помочь. Можете ли вы дать мне какую-то идею?
UPDATE: x и y составляет около 10 ^ 3, элементы - int. И нет равных множеств.