Как пересечь два отсортированных целочисленных массива без дубликатов?

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

Входные данные: Два отсортированных целочисленных массива A и B в порядке возрастания и разного размера N и M соответственно

Выходные данные: Отсортированный целочисленный массив C в порядке возрастания, содержащий элементы, которые появляются в обоих A и B

Ограничения: В C не допускаются дубликаты

Пример: Для ввода A = {3,6,8,9} и B = {4,5,6,9, 10,11}, на выходе должно получиться C = {6,9}

Всем спасибо за ответы! Подводя итог, можно сказать, что есть два основных подхода к этой проблеме:

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

Другой способ, которым мы могли бы это сделать, - это линейное сканирование одного из массивов с использованием двоичного поиска для поиска совпадения во втором массиве. Это будет означать время O (N * log (M)), если мы просканируем A и для каждого из его N элементов бинарный поиск на B (время O (log (M))).

Я реализовал оба подхода и провел эксперимент, чтобы увидеть, как они сравниваются (подробности можно найти здесь ). Кажется, что метод двоичного поиска выигрывает, когда M примерно в 70 раз больше, чем N, когда N имеет 1 миллион элементов.