仅使用数组结构查找数组中最大重复值的最快时间复杂度探讨

首先纠正一个误区：你提到的两次循环（先找最大值，再检查重复）的时间复杂度是O(n)，不是O(n²)。因为两次遍历都是线性扫描，总操作数是2n，属于线性时间复杂度范畴——O(n)的定义就是时间消耗和输入规模成线性比例。

能不能用单次循环实现O(n)时间复杂度？ #

可以，但需要借助额外的数组来做计数（前提是你知道数组元素的取值范围，比如元素都是非负整数且最大值不会太大）。具体逻辑：

• 单次遍历原数组时，同时完成两件事：
  1. 跟踪记录当前遇到的最大值max_val
  2. 用一个计数数组counts，以元素值为索引，每遇到一个元素就把对应索引的计数加1
• 遍历结束后，从max_val开始往下遍历计数数组，第一个计数≥2的元素就是最大的重复值

如果数组元素的取值范围极大（比如远大于数组长度n），这种计数数组的空间开销会很高，这时更务实的做法还是两次线性遍历：先找最大值，再统计它的出现次数；如果次数不足2，再找次大值，以此类推——这种情况最坏时间复杂度依然是O(n)，因为总遍历次数还是和n线性相关。

要是严格要求只能用原数组，不能额外开辟数组空间，那单次循环没法保证O(n)时间复杂度，最坏情况需要多次遍历，但平均情况可以做一些优化。不过题目说“仅使用数组作为数据结构”，应该只是禁止哈希表等非数组结构，额外数组是允许的，所以单次循环配合计数数组就能实现O(n)时间。

内容的提问来源于stack exchange，提问作者Jax