Определение пересечения между сложностью упорядоченных массивов

Question

Задача: Заданы два отсортированных массива A [] и B [] размера n каждый, проверьте, нет ли у них непустого пересечения (мне не нужно само пересечение, только решение)

Выполнение двоичного сортирования в B [] для каждого элемента A [] дает решение O (n lg n). Итерация каждого массива от начала до конца (выполнение чего-то очень похожего на Merge from Mergesort) дает решение O (n).

Мне было интересно, есть ли лучшее (с точки зрения сложности) решение. Я почти уверен, что нет, но я искал «эй, если вы дадите мне лучшее решение, я могу сортировать вектор в o (n lg n), что невозможно» -kind-of-argument

Answer 1

См. Снова проблему - "Given two sorted arrays ...".

Первоначальный предлагаемый вид не требуется, что приводит к решению O(n), чтобы выполнить процесс сортировки слиянием.

Вы не можете сделать намного лучше, чем процесс слияния типа, помните, что вы можете остановить раннее, если обнаружено пересечение.

Если они не были рассортированы:

Хэш-карта на основе решения будет технически быть O(n) - вставить все элементы из А в хэш-карте (O(n)). Делайте поиск для каждого из элементов в B (O(n)).

Для решения сортировки, поскольку вам нужно только решение, вам нужно только отсортировать A и выполнить цикл через B, выполнив поиск по O(log n) в A для каждого элемента в B и остановитесь, как только вы найдете элемент. Вы не будете делать лучше, чем O(n log n), но вы можете сократить до половины работы, если матч будет найден раньше.