algorithm - 交集算法 O(n) 更好的方法？

Question

令 S1 和 S2 为两组整数，使得 |S1| = |S2| = n。

所有整数都是从域 [1, 20n] 中获得的。给出一个算法在 O(n) 最坏情况时间内报告 S1 ∩ S2 中的所有整数。

我很困惑，他们为什么给我域名？ 我知道我可以在 O(n) + O(n) 时间内对两个列表进行计数排序，然后使用双指针方法在 O(n) 时间内比较元素。

我觉得我好像错过了什么或者有更好的方法？

Answer 1

您的方法可行，但我认为这是另一种比排序和迭代更简单的方法。它遵循计数排序或基数排序的想法，但略有不同。

1. 创建一个大小为 20n 的数组。
2. 遍历您的第一组和第二组并递增每个与您在刚刚创建的数组中的值相匹配的索引。
3. 遍历您创建的数组并打印出其中值为 2 的所有索引。

这是 O(n)。