本文详解如何仅用基础数组结构，在 o(n) 时间内一次性遍历完成最大值查找与重复计数，纠正“双重循环必为 o(n²)”的常见误解，并提供可直接运行的代码实现与关键注意事项。
本文详解如何仅用基础数组结构，在 o(n) 时间内一次性遍历完成最大值查找与重复计数，纠正“双重循环必为 o(n²)”的常见误解，并提供可直接运行的代码实现与关键注意事项。
在算法实践中，一个经典误区是将“两次独立遍历”错误等价于“嵌套循环”，从而误判时间复杂度。事实上，对同一数组执行两次顺序扫描（先找最大值、再统计其出现频次）属于串行操作，总时间复杂度仍为 O(n)，而非 O(n²)。这是因为：
- 第一次遍历：遍历 n 个元素，比较并更新 max → 时间 = O(n)
- 第二次遍历：再次遍历 n 个元素，统计 == max 的元素个数 → 时间 = O(n)
- 总耗时 = O(n) + O(n) = O(2n) = O(n)（常数因子在大 O 记号中被忽略）
✅ 正确实现示例（Java）：
public static int countMaxDuplicates(int[] arr) {
if (arr == null || arr.length == 0) return 0;
// Step 1: 找出最大值 —— 第一次 O(n) 遍历
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) max = arr[i];
}
// Step 2: 统计最大值出现次数 —— 第二次 O(n) 遍历
int count = 0;
for (int value : arr) {
if (value == max) count++;
}
return count;
}⚠️ 关键注意事项：
- 不可合并为单次遍历？其实可以，但非必须：虽可通过一次遍历同时维护 max 和 count（如遇更大值则重置计数；遇相等值则累加），但逻辑稍复杂且不改变渐进复杂度。双遍历更清晰、易验证、不易出错，符合“简单即可靠”的工程原则。
- 空间限制严格：本方案仅使用常量额外空间（max, count, 循环变量），完全满足“仅用数组”要求，无需哈希表、集合等辅助结构。
- 边界鲁棒性：务必检查空数组或 null 输入，避免运行时异常。
? 总结：面对“仅限数组”的约束，O(n) 是理论最优解——既无法低于 O(n)（必须至少读取每个元素一次），也无需牺牲可读性追求微小常数优化。掌握“串行遍历 ≠ 嵌套复杂度”这一核心认知，是准确分析算法性能的基础能力。
