как найти элементы, присутствующие во всех трех списках (наиболее эффективно)

Я использую C#, и у меня есть три List<int> (скажем, одинакового размера n и различных элементов). Моя цель — найти элементы, присутствующие во всех трех. Поэтому я мог бы перебрать первый и проверить, есть ли элемент в двух других. Это будет O(n^2). Я мог бы сначала отсортировать два других списка, а затем проверить наличие элементов в них с помощью двоичного поиска. Это будет O(nlogn) (без сортировки). Или я мог бы создать два словаря Dictionary<int, byte>, где ключом был бы элемент моего списка, а затем проверка элемента была бы O(1) и всего O(n). А как насчет цены создания словаря? Кто-нибудь может сказать, сколько это стоит?

Также, возможно, есть еще более эффективный алгоритм?


dictionary c# algorithm
person ren    schedule 28.03.2014    source источник
comment
Содержат ли эти списки элементы в каком-то порядке или они неупорядочены?   -  person Dmitry    schedule 28.03.2014
comment
HashSet‹int› имеет некоторые преимущества для этой задачи.   -  person user3449857    schedule 28.03.2014
comment
Решение HashSet или LINQ явно лучше. Если бы вы сортировали списки, вы бы не выполняли бинарный поиск, а выполняли бы трехстороннее слияние и сохраняли бы только элементы с дубликатами. Это будет O (n log n) для сортировки и O (n log 3) для слияния.   -  person Jim Mischel    schedule 28.03.2014

Ответы (2)


arrow_upward
4
arrow_downward

Использование HashSet довольно просто, и я думаю, что это будет лучшим выбором для повышения производительности.

HashSet<T> hset = new HashSet<T>(list1);
hset.IntersectWith(list2);
hset.IntersectWith(list3);
return hset.ToList(); // skip the ToList() if you don't explicitly need a List
person Kendall Frey    schedule 28.03.2014
comment
Или, чтобы упростить с помощью LINQ: var rslt = list1.Intersect(list2).Intersect(list3).ToList(); - person Jim Mischel; 28.03.2014
comment
Я тоже об этом думал, но решил, что явное HashSet будет не менее быстрым. - person Kendall Frey; 28.03.2014
comment
Решение HashSet может быть немного быстрее, хотя LINQ будет использовать HashSet (или его эквивалент) внутри. Я считаю, что версия LINQ несколько проще для понимания. И помогает то, что его легче печатать. В основном это сводится к вопросу стиля. - person Jim Mischel; 28.03.2014

arrow_upward
1
arrow_downward

Вы можете использовать только один Dictionary<int, byte>, где значение byte может быть 1 или 2. Для первого списка вы просто выполняете вставку со значением, равным 1, а для второго списка вы делаете TryGetValue и на основе результата либо вставляете, либо обновляете значение, равное 2. Для третьего списка вы проверяете, равно ли значение 2.

person Dialecticus    schedule 28.03.2014