我正在做“算法分析”的任务，我被这个问题困住了，我明天必须提交，我需要帮助。如果你能解决这个问题，请回答。
给定一个包含 n 个数字的数组 A，编写一个有效的算法来找到该数组中最常出现的元素（该数组的模式）。还要分析算法的时间复杂度。
问问题
387 次
1 回答
1
由于这是一项作业，我将仅向您提示复杂性的上限和类似问题。
这个问题比Element Distinctness Problem 1更难一些。元素区别问题被称为不能比O(nlogn)最坏情况更好地解决。元素区别的解决方案是：
- 排序和迭代 -
O(nlogn) - 创建元素的集合/直方图并检查唯一性。这是在平均情况和最坏情况下使用哈希表以及额外空间来完成的。
O(n)O(n^2)O(n)
考虑这两种方法，并尝试考虑如何修改它们以解决您的问题。
此外，元素独特性的下限告诉您不会有比O(nlogn)最坏情况更好的算法。
(1) Element Distinctness 问题：数组中的所有元素都是不同的吗？或者是否有任何元素也有自己的副本？
于 2014-11-25T12:45:31.417 回答