Вычислительный набор пересечения в линейное время?

Question

Есть ли алгоритм, который, учитывая два набора, вычисляет их пересечение в линейное время?

Я могу запустить два цикла for, чтобы проверить все пары элементов, записывая элементы, которые я нахожу в обоих изнаборы.Однако время выполнения будет O (n ² ).Как мне сделать это за O (n) раз?

Answer 1

Это зависит от вашей реализации набора.

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

Если у вас есть набор деревьев (O (LG N) поиск), то этот подход будет работать, но он выполняется в O (N LG N) времени. Ты можешь лучше; есть решение O (n). Я предполагаю, что у вас есть какой-то итератор, который может проходить элементы двух множеств в порядке возрастания. Если вы это сделаете, то вопрос «даны два списка в отсортированном порядке, найдите их пересечение». Это можно сделать, используя модифицированную версию алгоритма, который вы используете для объединения двух диапазонов. Идея состоит в том, чтобы отслеживать два итератора. На каждом шаге сравнивайте первые элементы диапазонов. Если они равны, добавьте элемент к пересечению и продвиньте оба итератора вперед. Если первый меньше второго, тогда продвиньте первый итератор. Если первый элемент больше, продвиньте второй итератор. Это выполняется за время O (n), потому что каждая итерация потребляет как минимум один элемент, а всего O (n) элементов.

Answer 2

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

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

O(n)

Answer 3

Объедините два массива и посчитайте количество вхождений каждого элемента в этом объединенном массиве и поместите их в новый массив.Затем проверьте этот массив подсчета для записей, которые содержат 2, эти элементы находятся в пересечении двух наборов.

Answer 4

intersection(a, b):
  result = new empty set
  for x in b:
    if a contains x:
      add x to result

  return result

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

Answer 5

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

FUNCTION: INTERSECTION ( LIST A, LIST B )
{
   CREATE C AS EMPTY LIST

   FOR EVERY: NUMBER n IN A
   {
        IF BINARY-SEARCH(n) IN B
        {
            ADD n TO C
        }
   }

   RETURN C
}

Time Complexity = O(n O(BINARY-SEARCH)) = O(n log n)

если список B равен hashed, то мы имеем BIG-THETA(C n + T(hash))

где BIG-THETA - среднее асимптотическое, а C - constant T(hash) - время, необходимое для хэш-функции

.

Answer 6

Для всех элементов в наборе 1: проверьте, находится ли этот элемент в наборе 2. Вы можете реализовать набор, который имеет время поиска O (1).