给定一个未排序的数组，A[]，包含n整数，如何创建一个算法来返回出现最频繁的元素?
我想你需要一种方法来计算一个元素出现的次数。我只能算出一个O(n2)实现。我知道我需要先使用排序算法，但如果我要使用归并排序，这已经是O(n logn))的总运行时间。我只对数据进行了排序，如果不进一步增加运行时间，我就无法查看元素。
对数组进行排序，然后，所有重复元素彼此相邻。
简单地迭代数组，同时持有maxSeen和currSeen计数器，如果当前元素等于最后一个元素，则增加currSeen，否则-重置currSeen，并替换maxSeen，如果currSeen大于它。
排序为O(nlogn)，迭代一次为O(n)，所以O(nlogn + n) = O(nlogn)
这是家庭作业，所以遵循这个指导方针来创建代码应该是你的任务。好运！
作为旁注，由于这至少和元素区别性问题一样难，并且使用基于比较的算法，它不能比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)取一个字典，将其中的每个数字存储为键，并将value作为其计数，如果数字重复，则初始值为1，否则将其输入到字典中。
遍历字典中每个大于它的键值它的键值将是所有
中最大的解为n+n =2n ~> n