Каков самый быстрый алгоритм для пересечения двух отсортированных списков?

Question

Скажите, что есть два отсортированных списка: A и B.

Количество записей в A и B может варьироваться. (Они могут быть очень маленькими/огромными. Они могут быть похожими друг на друга/существенно отличаются).

Как известно, это самый быстрый алгоритм для этой функции?

Может ли кто-нибудь дать мне идею или ссылку?

Answer 1

Предположим, что A имеет m элементы и B имеет n элементы, с m ≥ n. Информация теоретически, лучшее, что мы можем сделать, это

(m + n)! 
lg -------- = n lg (m/n) + O(n) 
    m! n! 

сравнения, так как для того, чтобы проверить пустое пересечение, мы по существу должны выполнить отсортированный слияния. Мы можем получить постоянный коэффициент этой привязки путем повторения через B и сохранения «курсора» в A с указанием позиции, в которой должен быть вставлен последний элемент B для поддержания упорядоченного порядка.Мы используем exponential search для перемещения курсора, на общую сумму, которая по заказу

lg x_1 + lg x_2 + ... + lg x_n, 

где x_1 + x_2 + ... + x_n = m + n есть некоторое целое число раздел m. Эта сумма составляет O(n lg (m/n)) по объему lg.

Answer 2

Допустим, есть 2 Списки А и В с целыми

for(int i = A.size() - 1; i > -1; --i){ 
    Integer currentInteger = A.get(i); 
    if(!B.remove(currentInteger)) 
     A.remove(currentInteger); 
} 

Answer 3

Я не знаю, если это самый быстрый вариант, но вот один, который работает в O(n+m) где n и m являются размеры списков:

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

Answer 4

Что такое, как известно, самый быстрый алгоритм для этой функции?

Используйте merge sort метод, который лучше всего, когда два списка отсортирован. Для получения объединенного списка сортировки потребуется O(n+m).

Вы не можете сортировать эти два списка без прохождения каждого из них. Таким образом, лучшее, что вы можете достичь, - O(n+m).

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