Как найти общие элементы из n массивов

Question

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

Answer 1

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

Answer 2

Перебирайте каждую из них и используйте хеш-таблицу для хранения счетчиков. Ключ - это значение целого числа, а значение - количество появлений.

Answer 3

Это зависит.Если один набор существенно меньше другого или по какой-то другой причине вы ожидаете, что пересечение будет довольно разреженным, тогда двоичный поиск может быть оправдан.В противном случае, вероятно, проще всего пройти через оба сразу.Если текущий элемент в одном элементе меньше, чем в другом, перейдите к следующему элементу в этом массиве.Когда / если вы получаете равные элементы, вы отправляете это как вывод и переходите к следующему элементу в обоих массивах.(Это предполагает, что, как вы и предлагали, вы, конечно, уже отсортировали оба).

Это операция O (N + M), где N - размер одного массива, а M - размер.другого.Используя бинарный поиск, вы получаете O (N lg ₂ M) вместо этого, что может быть меньшей сложностью, если один массив намного меньше другого, но, скорее всего, будет чистый убыток, если они близкик одному и тому же размеру.

В зависимости от того, что вам нужно / нужно, версии, которые пытаются просто подсчитать вхождения, могут вызвать довольно существенную проблему: если в одном массиве несколько вхождений одного элемента, они все равно будутпосчитайте это как два вхождения этого элемента, указывая на пересечение, которое на самом деле не существует.Вы можете предотвратить это, но это сделает задачу несколько менее тривиальной - вы вставляете элементы из одного массива в вашу хеш-таблицу, но всегда устанавливаете счетчик на 1. Когда это закончено, вы обрабатываете второй массив, устанавливая счетчик на 2если и только если элемент уже присутствует в таблице.

Answer 4

Определите «лучший».

Если вы хотите сделать это быстро, вы можете сделать это O (n), просматривая каждый массив и сохраняя счет для каждого уникального элемента.Детали того, как считать уникальные элементы, зависят от алфавита вещей, которые могут быть в массиве, например, он редкий или плотный?

Обратите внимание, что это число O (n) в количестве массивов, ноO ( nm ) для массивов длины m ).

Answer 5

Лучший способ, вероятно, состоит в том, чтобы хэшировать все значения и вести подсчет вхождений, отбирая все, что не произошло i раз, когда вы проверяете массив i, где i = {1, 2, ..., n}.К сожалению, ни один детерминированный алгоритм не может дать вам менее O(n*m) времени выполнения, поскольку это невозможно сделать без проверки всех значений во всех массивах, если они не отсортированы.

Более быстрый алгоритм долженлибо иметь приемлемый уровень вероятности (Монте-Карло), либо полагаться на какое-то известное состояние списков для проверки только подмножества элементов (т. е. вас интересуют только те элементы, которые встречались во всех i-1 предыдущих списках при рассмотрении i список, но в несортированном списке поиск элементов нетривиален.