如何从n个数组中找到公共元素

Question

我在考虑排序然后进行二分搜索。这是最好的方法吗？

Answer 1

我在这种情况下主张散列：您将有时间与两个数组的常见大小成比例。
由于大多数主要语言都在其标准库中提供散列表，我几乎不需要展示如何实现这样的解决方案。

Answer 2

定义“最佳”。

如果你想快速做到这一点，你可以通过遍历每个数组并保持每个唯一元素的计数来完成O（n）操作。如何计算独特元素的细节取决于数组中可能存在的事物的字母表，例如它是稀疏还是密集的？

注意，这是在阵列的数目为O（n），但O（纳米）为长度米）的阵列。

Answer 3

遍历每一个并使用散列表来存储计数。关键是整数值，值是出现次数。

Answer 4

这取决于。如果一个集合比另一个要小得多，或者由于某种其他原因，你期望交集非常稀疏，那么二分查找可能是合理的。否则，可能最容易一次完成两个步骤。如果一个中的当前元素小于另一个中的元素，则前进到该数组中的下一个项目。当/如果得到相同的元素，则将其作为输出发送，然后前进到两个数组中的下一个项目。 （这个假设，就像你所倡导的那样，当然你已经对这两者进行了排序）。

这是一个O（N + M）操作，其中N是一个数组的大小，M是另一个的大小。使用二进制搜索，您可以获得O（N lg M），如果一个数组比另一个数组小，可能会降低复杂性，但如果它们接近相同大小，则可能会造成净损失。

根据您需要/想要的版本，试图计算出现次数的版本可能会导致相当大的问题：如果在一个数组中出现多次单个项目，它们仍会将此次数计为两次项目，表明一个并不存在的交集。您可以防止这种情况，但这样做会使作业稍微不重要 - 您将一个数组中的项插入到散列表中，但始终将计数设置为1.完成后，通过将计数设置为2来处理第二个数组当且仅当该项目已经存在于该表格中时。

Answer 5

最好的方法是哈希所有的值并保持发生次数，剔除所有没有发生的事情i次当您检查数组i其中i = {1, 2, ..., n}。不幸的是，没有确定性算法可以让你的运行时间小于O(n*m)，因为如果不排除所有数组中的所有值，就不可能做到这一点。

一个更快的算法需要有一个可接受的概率水平（蒙特卡洛），或者依靠一些已知的列表条件来检查只有一部分元素（即你只关心所有发生在i-1以前的列表在考虑i列表时，但在未排序的列表中，搜索元素并不重要。