Найти общий элемент в N массивах

Question

Если у меня есть N массивов, какой самый лучший (сложность времени. Пространство не важно) способ найти общие элементы. Вы можете просто найти 1 элемент и остановиться.

Редактировать: все элементы являются числами.

Редактировать: это не отсортировано. Пожалуйста, не сортируйте и не сканируйте.

Это не проблема домашней работы. Кто-то задал мне этот вопрос давным-давно. Он использовал хеш для решения проблемы и спросил меня, есть ли у меня лучший способ.

Answer 1

Создание хеш-индекса с элементами в качестве ключей, считается как значения. Переберите все значения и обновите счет в индексе. Затем просмотрите индекс и проверьте, какие элементы имеют число = N. Поиск элемента в индексе должен быть O (1), в сочетании с циклическим просмотром всех элементов M должно быть O (M).

Если вы хотите сохранить порядок, определенный для определенного входного массива, зациклите этот массив и проверьте количество элементов в индексе в этом порядке.

Некоторые особые случаи:

если вы знаете, что элементы являются (положительными) целыми числами с максимальным числом, которое не слишком велико, вы можете просто использовать обычный массив в качестве индекса "хеша", чтобы вести счет, где число - это просто индекс массива. 1009 *

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

РЕДАКТИРОВАТЬ когда я ответил на вопрос, в вопросе не было части "лучшего способа", чем хэширование.

Answer 2

Я не думаю, что подход, предложенный catchmeifyoutry, сработает.

Допустим, у вас есть два массива 1: {1,1,2,3,4,5} 2: {1,3,6,7}

тогда ответ должен быть 1 и 3. Но если мы используем подход с хеш-таблицей, 1 будет иметь счет 3, и мы никогда не найдем 1 в его ситуации.

Также проблемы становятся более сложными, если мы введем что-то вроде этого: 1: {1,1,1,2,3,4} 2: {1,1,5,6}

Здесь я думаю, что мы должны дать вывод как 1,1. Предложенный подход не работает в обоих случаях.

Решение:

прочитать первый массив и поместить в хеш-таблицу. Если мы снова найдем тот же ключ, не увеличивайте счетчик. Читайте второй массив таким же образом. Теперь в хеш-таблице у нас есть общие элементы, которые имеют значение 2.

Но опять-таки этот подход потерпит неудачу во втором наборе ввода, который я дал ранее.

Answer 3

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

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

Answer 4

Сначала я бы начал с вырожденного случая, чтобы найти общие элементы между двумя массивами (подробнее об этом позже). Оттуда у меня будет набор общих значений, которые я буду использовать в качестве самого массива и сравнивать его со следующим массивом. Эта проверка будет выполняться N-1 раз или до тех пор, пока массив «нести» общих элементов не уменьшится до размера 0.

Можно было бы ускорить это, я мог бы себе представить, разделяя и властвуя, разбивая N массивов на конечные узлы дерева. Следующий уровень вверх по дереву - это N / 2 общих элементов и т. Д. И т. Д. До тех пор, пока в верхней части не будет заполнен массив или нет. В любом случае у вас будет свой ответ.

Без сортировки и сканирования наилучшая рабочая скорость, которую вы получите для сравнения двух массивов для общих элементов, равна O (N ² ).

Answer 5

Самый прямой способ - пересечь первые 2 массива, а затем пересечь это пересечение с остальными массивами N-2.

Если «пересечение» не определено на языке, на котором вы работаете, или вам требуется более конкретный ответ (т. Е. Вам нужен ответ «как вы делаете пересечение»), то измените свой вопрос как таковой.

Без сортировки не существует оптимизированного способа сделать это на основе предоставленной информации. (т.е. сортировка и размещение всех элементов относительно друг друга, затем итерация по длине массивов, проверка на наличие определенных элементов во всех массивах одновременно)