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

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

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

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

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

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

Используйте хэш-таблицу, отображающую объекты в счетчики частоты. Перебирайте все три списка, увеличивая количество вхождений в хеш-таблице, пока не встретите один с количеством вхождений 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()

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

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

• Сортировать один массив - время 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 ....

Пусть 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. бросаем новое исключение InvalidDataGivenByInterviewerException();

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