在O(n log n)的时间内统计数组中出现的次数。

Question

给定一个未排序的数组A[]，包含n个整数，如何创建一个算法来返回出现最频繁的元素？我认为你需要一种方法来计算元素出现的次数。但我只能想出一个O(n^2)的实现方式。我知道我需要先使用排序算法，但如果我使用归并排序，那么总运行时间已经是O(n logn)了。我只是对数据进行了排序，还不能查看元素，否则会进一步增加运行时间。

- user4567366

---

如果可以对数组进行排序，归并排序是一个不错的选择，时间复杂度为n logn，之后进行简单的n次迭代即可完成。 - Daniel Mendel

不是答案，而是线索。O(n log n) + O(n) 仍然是 O(n log n)。大O符号只关心主导项。 - David Conneely

@DavidC 我以为你会把它们相乘，而不是相加！如果我知道的话，我就不会问这个问题了。谢谢！ - user4567366

Answer 1

将数组排序，这样所有重复的元素就会在一起。
简单地迭代该数组，同时保持maxSeen和currSeen计数器，如果当前元素等于上一个元素，则增加currSeen，否则 - 重置currSeen，如果currSeen大于maxSeen，则替换maxSeen。

排序是 O(nlogn)，一次迭代是O(n)，因此总共是O(nlogn + n) = O(nlogn)

这是一份作业，因此按照这些指导创建代码应该是您的任务。祝好运！

---

作为副产品，由于这至少与元素不同性问题一样困难，并且使用基于比较的算法不能比O(nlogn)更好地完成。

---

另外，可以使用哈希表在O(n)时间+空间内完成。
创建数据的直方图，即哈希映射，其中键是一个元素，值是出现次数。然后，该问题降解为在此哈希表中查找最大值。
平均情况下构建表是O(n)，查找最大值是O(n)。

然而，这使用了O(n)额外的内存，并且在最坏的情况下可能会恶化到O(n^2)时间。

- amit

---

我之前没有听说过元素唯一性问题。感谢您包含了那个链接！ - templatetypedef

@templatetypedef 请再看第二个链接，它指向证明使用代数树模型的下限的文章。(当然，可以使用哈希在O(n)平均时间和空间内完成，但不能使用比较) - amit

Answer 2

您的推测是正确的，首先对数组进行排序是个好主意。正如您所指出的，这将花费O(n log n)的时间。然后，您可以扫描数组，并逐个计算每个值的频率，同时记住最常见的值。这将花费O(n)的时间。总成本为O(n log n + n)，属于O(n log n)。

为了理解原因，请考虑O(2n log n)。这显然属于O(n log n)，因为2n log n在常数因子内与n log n相近。并且n log n + n上界为2n log n，因此它也属于O(n log n)。

- Michael Laszlo

---

我没有意识到你会将这两个运行时间相加，而不是相乘。那是我的糊涂。非常感谢！ - user4567366

Answer 3

只需使用字典将每个数字存储为键，初始值为1作为其计数。如果数字再次重复，则增加该计数，否则将其输入到字典中。

遍历字典中值大于其键的每个键值，其中值最大。

解决方案为n + n = 2n ~> n。

- xoxocoder

---

请注意，这是一个四年前的问题，已经有了被接受的答案。哈希映射/字典建议已经在被接受的答案中提到了。 - Sameer Naik