Похожие элементы из списков

Question

С учетом N списков из M номеров в каждом списке мы должны найти ОДИН элемент из каждой группы, такой каждая пара ai aj дает | ai-aj | как можно меньше.

Например у нас есть 3 списка

{12,16,67,43}

{7,17,68,48}

{14,15,77,54}

И чтобы минимизировать результат, мы должны выбрать № 16 из списка 1 № 17 из списка 2 № 15 из списка 3 так что

|16-17|=1
|16-15|=1
|17-15|=2 

так что наш результат: 2

Как решить это быстро? в N * M время? или войдите что-нибудь время

Chris

Answer 1

Если вы используете линейный поиск, сложность составляет O (N * M) для одного совпадения (т. Е. Для каждого элемента в наборе j, выполните линейный поиск для наиболее похожего элемента из набора i, и выберите наименьшее из эти результаты.

Если вы сначала отсортируете каждый набор, вы получите (как минимум) O (N log N) + O (M log M) для сортировки и O (M log N) для поиска (где N - число элементов в множестве i, а M количество элементов в множестве j). Если вы пройдете через два набора вместе, вы, вероятно, сможете уменьшить это значение до O (N + M) для комбинированного поиска.