Алгоритм поиска дубликатов в нескольких связанных списках

Question

Какой самый быстрый метод поиска дубликатов в нескольких (больших) связанных списках.Вместо этого я попытаюсь проиллюстрировать проблему с массивами, чтобы сделать ее более читабельной.(Я использовал цифры от 0 до 9 для простоты вместо указателей).

list1[] = {1,2,3,4,5,6,7,8,9,0};
list2[] = {0,2,3,4,5,6,7,8,9,1};
list3[] = {4,5,6,7,8,9,0,1,2,3};
list4[] = {8,2,5};
list5[] = {1,1,2,2,3,3,4,4,5,5};

Если я сейчас спрашиваю: «существует ли число 8 в списке 1-5?»Я мог бы отсортировать списки, удалить дубликаты, повторить это для всех списков и объединить их в «суперсписок» и посмотреть, равно ли количество (новых) дубликатов числу списков, которые я просматриваю.Предполагая, что я получил правильное количество дубликатов, я могу предположить, что то, что я искал (8), существует во всех списках.Если бы я вместо этого искал 1, я получу только четыре дубликата, поэтому он не найден во всех списках.

Существует ли более быстрый / более умный / лучший способ достичь вышеуказанного без сортировки и / или изменения списков вв любом случае?

PS: Этот вопрос задается в основном из чистого любопытства и больше ничего!:)

Answer 1

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

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

Answer 2

Определите массив hash и установите для всех значений местоположения значение 0

define hash[MAX_SYMBOLS] = {0};
define new_list[LENGTH]
defile list[LENGTH] and populate

Теперь для каждого элемента в вашем list используйте это число в качестве индекса в hash и увеличьте это местоположениеhash.Каждое присутствие этого числа будет увеличивать значение в этом hash местоположении один раз.Таким образом, дублированное значение i будет иметь hash[i] > 1

for i=0 to (n - 1)
  do
    increment hash[list[i]]
endfor

Если вы хотите удалить дубликаты и создать новый список, то просканируйте массив hash и для каждого присутствия i, т.е.если hash[i] > 0 загрузить их в новый список в том порядке, в котором они появились в исходном списке.

define j = 0
for i=0 to (n - 1)
  do
    if hash[list[i]] is not 0
      then
        new_list[j] := i
        increment j
    endif
endfor

Обратите внимание, что при использовании с отрицательными числами вы не сможете использовать значения непосредственно для индексации,Чтобы использовать отрицательные числа, сначала мы можем найти наибольшую величину отрицательных чисел и использовать эту величину для добавления ко всем числам, когда мы используем их для индексации массива hash.

find the highest magnitude of negative value into min_neg

for i=0 to (n - 1)
  do
    increment hash[list[i + min_neg]]
endfor

Или в реализацииВы можете выделить непрерывную память, а затем определить указатель на середину выделенного блока памяти, чтобы вы могли перемещаться как в прямом, так и в обратном направлении, чтобы вы могли использовать с ним отрицательный индекс.Вы должны убедиться, что у вас достаточно памяти для использования перед и сзади указателя.

int *hash = malloc (sizeof (int) * SYMBOLS)
int *hash_ptr = hash + (int)(SYMBOLS/2)

теперь вы можете сделать hash_ptr[-6] или немного hash_ptr[i] с -SYMBOLS/2 < i < SUMBOLS/2 + 1

Answer 3

Вопрос немного расплывчатый, поэтому ответ зависит от того, что вы хотите.

Хеш-таблица - это правильный ответ для общих вопросов о дубликатах, поскольку она позволяет просматривать каждый список только один раз.составить таблицу, которая ответит на большинство вопросов;однако для некоторых вопросов такой вопрос не требуется.

Возможные случаи, которые могут ответить на ваш вопрос:

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

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

Вам нужен номердубликатов в каждой таблице отдельно?- Умножьте каждое значение на количество списков и добавьте номер обрабатываемого списка.Сохраните это как ключ хеша и посчитайте дубликаты.Когда все списки обработаны, у вас есть таблица, которая может ответить на все виды вопросов.Чтобы проверить дубликаты на определенное значение, умножьте его на счетчик списка и проверьте последовательные ключи хеша.Если есть один для каждого списка, номер присутствует в каждом списке.Если все значения больше 1 в этом диапазоне, число дублируется в каждом списке.

И т. Д.