本文详解如何仅用基础数组结构，在 o(n) 时间内完成“查找数组中最大值出现次数”的任务，纠正常见的时间复杂度误解，并提供可直接运行的实现代码与关键注意事项。
本文详解如何仅用基础数组结构，在 o(n) 时间内完成“查找数组中最大值出现次数”的任务，纠正常见的时间复杂度误解，并提供可直接运行的实现代码与关键注意事项。
在算法实践中，一个常见误区是将“两次独立遍历”错误地等同于嵌套循环——从而误判时间复杂度为 O(n²)。事实上，对同一数组先后执行两次单层 for 循环，其总体时间复杂度仍为 O(n)，因为：
- 第一次遍历（找最大值）：访问 n 个元素 → O(n)
- 第二次遍历（统计该最大值出现频次）：同样访问 n 个元素 → O(n)
- 总代价 = O(n) + O(n) = O(2n) = O(n)（常数因子在渐进分析中被忽略）
因此，无需哈希表、排序或额外高级数据结构，仅靠纯数组和两次线性扫描，即可高效解决该问题。
以下是简洁、健壮的 Java 实现示例：
public static int countMaxDuplicates(int[] arr) {
if (arr == null || arr.length == 0) {
throw new IllegalArgumentException("Array must be non-empty");
}
// Step 1: Find the maximum value in one pass
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
// Step 2: Count occurrences of max in another pass
int count = 0;
for (int value : arr) {
if (value == max) {
count++;
}
}
return count;
}✅ 正确性保障：两次遍历逻辑正交、无依赖，可安全分离；
⚠️ 注意事项：
- 输入校验不可省略——空数组或 null 会导致运行时异常；
- 若需同时返回最大值及其频次，可封装为 Map.Entry
或自定义类，但不改变时间复杂度； - 该解法空间复杂度为 O(1)，仅使用常量级额外变量，符合“仅用数组”的约束要求；
- 即使数组含负数、重复最大值分散在首尾，算法依然正确（例如 [-5, 3, 1, 3, -2, 3] 返回 3）。
总结而言，本题的最优解就是“两趟扫描”——它不仅是可行的，更是理论最优：因为至少需要读取每个元素一次以确认全局最大值，而确认后又需再次检查所有元素以计数，故 Ω(n) 是下界，O(n) 即为紧确界。所谓“必须用哈希表才快”，实为对基础时间复杂度分析的常见误读。
