给出一个包含A[]个整数的未排序数组n，如何创建一种算法来返回最常出现的元素？
我想您需要一种方法来计算元素发生的次数。我只能弄清楚O（n 2）实现。我知道我需要首先使用排序算法，但是如果要使用合并排序，则已经是O（n logn））的总运行时间。我仅对数据进行了排序，并且在不增加运行时间的情况下无法查看元素。
对数组进行排序，然后，所有重复元素都彼此相邻。在持有maxSeen和currSeen计数器的同时，简单地迭代数组，如果当前元素等于最后一个元素，则增加currSeen，否则-重置currSeen，如果maxSeen大于它，则替换currSeen 。
排序为O（nlogn），并且迭代一次为O（n），所以总计O(nlogn + n) = O(nlogn)
这是家庭作业，因此，按照此准则创建代码应该是您的任务。祝你好运！
作为旁注，由于使用基于比较的算法，这至少与Element Distinctness Problem和it cannot be done better than O(nlogn)一样困难。
旁注二，可以使用哈希表在O(n)时间+空间中完成。创建数据的直方图，该直方图是一个哈希图，其中的键是元素，值是出现次数。然后，问题恶化为在此哈希表中找到最大值。建立表是O(n)的平均情况，找到最大值是O(n)。
但是，这会使用O(n)额外的内存，在最坏的情况下，它可能会恶化到O(n^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）中。
只需将字典中的每个数字都存储为键，如果重复的数字再次增加该值，则将其值初始为1，否则将其输入dict。
遍历字典中值较大的每个键值，键在所有键中将最大
解决n + n = 2n〜> n