如何查找所有三个列表中存在的元素(最有效)

本文关键字：列表 存在 元素 有效 三个 何查找 查找 | 更新日期: 2023-09-27 17:54:23

我使用c#，我有三个List<int>(比如大小相等的n和不同的元素)。我的目标是找到这三者中存在的元素。所以我可以遍历第一个然后检查item是否在另外两个里面。也就是O(n²)我可以先对另外两个列表进行排序，然后使用二分搜索来检查其中的项。也就是O(nlogn)(不排序)或者我可以构造两个字典Dictionary<int, byte>，其中键是列表的项，然后检查一个项将是O(1)和总O(n)。但是构建字典的成本是多少呢?谁能告诉我那要花多少钱吗?

也可能有更有效的算法?

如何查找所有三个列表中存在的元素(最有效)

使用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

您只能使用一个Dictionary<int, byte>，其中byte的值可以为1或2。对于第一个列表，您只需执行值为1的插入操作，对于第二个列表，您执行TryGetValue，并根据结果执行值为2的插入或更新操作。对于第三个列表，检查value是否为2。

相关文章：