Найти уникальный общий элемент из 3 массивов

Question

Оригинальная проблема:
У меня есть 3 коробки, каждая из которых содержит 200 монет, учитывая, что только один человек звонил из всех трех коробок, и поэтому в каждой коробке есть одна монета с одинаковыми отпечатками пальцев, а у остальных монет разные отпечатки пальцев. Вы должны найти монету, которая содержит один и тот же отпечаток пальца во всех 3 коробках. Так что мы можем найти отпечаток пальца человека, который сделал звонок из всех трех ящиков.

Конвертированная задача:
У вас есть 3 массива, содержащих по 200 целых чисел в каждом. Учитывая, что в этих 3 массивах есть один и только один общий элемент. Найдите общий элемент.
Пожалуйста, подумайте над решением этой проблемы за исключением тривиального пространства O (1) и времени O (n ^ 3).

Answer 1

Некоторое улучшение в ответе Пелконена:
Из преобразованной задачи в ОП:

«Учитывая, что в этих трех массивах есть один и только один общий элемент». Нам нужно отсортировать только 2 массива и найти общий элемент.

Answer 2

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

Answer 3

Пусть N = 200, k = 3,

1. Создание хеш-таблицы H с емкостью ≥ Nk.

2. Для каждого элемента X в массиве 1 установите H [X] в 1.

3. Для каждого элемента Y в массиве 2, если Y находится в H и H [Y] == 1, установить H [Y] = 2.

4. Для каждого элемента Z в массиве 3, если Z находится в H и H [Z] == 2, вернуть Z.

5. throw new InvalidDataGivenByInterviewerException();

O (Nk) время, O (Nk) пространственная сложность.

Answer 4

Использование хеш-таблицы для сопоставления объектов с частотами. Перебирайте все три списка, увеличивая количество вхождений в хеш-таблице, пока не встретите один с числом вхождений 3. Это O (n), поскольку сортировка не требуется. Пример на Python:

def find_duplicates(*lists):
  num_lists = len(lists)
  counts = {}
  for l in lists:
    for i in l:
      counts[i] = counts.get(i, 0) + 1
      if counts[i] == num_lists:
        return i

Или эквивалент, используя наборы:

def find_duplicates(*lists):
  intersection = set(lists[0])
  for l in lists[1:]:
    intersection = intersection.intersect(set(l))
  return intersection.pop()

Answer 5

Используйте хеш-таблицу для каждого целого числа и закодируйте записи так, чтобы вы знали, из какого массива он исходит, - затем проверьте слот, в котором есть записи из всех 3 массивов. О (п)

Answer 6

Если вы хотите самый быстрый * ответ:

• Сортировать один массив - время равно N log N.
• Для каждого элемента во втором массиве ищите первый. Если вы найдете его, добавьте 1 в сопутствующий массив; в противном случае добавьте 0 - время равно N log N, используя пробел N.
• Для каждого ненулевого отсчета скопируйте соответствующую запись во временный массив, сжав его так, чтобы он все еще сортировался - время равно N.
• Для каждого элемента третьего массива ищите временный массив; когда вы найдете удар, остановитесь. Время меньше чем N log N.

Вот код в Scala, который иллюстрирует это:

import java.util.Arrays

val a = Array(1,5,2,3,14,1,7)
val b = Array(3,9,14,4,2,2,4)
val c = Array(1,9,11,6,8,3,1)

Arrays.sort(a)
val count = new Array[Int](a.length)
for (i <- 0 until b.length) {
  val j =Arrays.binarySearch(a,b(i))
  if (j >= 0) count(j) += 1
}
var n = 0
for (i <- 0 until count.length) if (count(i)>0) { count(n) = a(i); n+= 1 }
for (i <- 0 until c.length) {
  if (Arrays.binarySearch(count,0,n,c(i))>=0) println(c(i))
}

С немного большей сложностью вы можете либо не использовать дополнительное пространство за счет того, чтобы быть еще более разрушительным по отношению к своим исходным массивам, либо вообще не трогать свои исходные массивы за счет другого пространства N.

---

Редактировать: * как отмечалось в комментариях, хеш-таблицы быстрее для не порочных входных данных. Это «самый быстрый худший случай». Худший случай не может быть настолько маловероятным, если вы не используете действительно хороший алгоритм хеширования, который может съесть больше времени, чем ваш. Например, если вы умножите все свои значения на 2 ^ 16, тривиальное хеширование (т. Е. Просто использование целого числа с битовой маской в ​​качестве индекса) будет сталкиваться каждый раз в списках короче 64k ....

Answer 7

O (N) решение: используйте хеш-таблицу. H [i] = список всех целых чисел в трех массивах, которые отображаются в i.

Для всех H [i]> 1 проверьте, совпадают ли три его значения. Если да, у вас есть решение. Вы можете сделать эту проверку даже с наивным решением, оно все равно должно быть очень быстрым, или вы можете отсортировать эти H [i], и тогда оно станет тривиальным.

Если ваши числа относительно невелики, вы можете использовать H [i] = k, если i появляется три раза в трех массивах, тогда решением будет i, для которого H [i] = 3. Если ваши числа огромны используйте хеш-таблицу, хотя.

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