本文介绍如何仅使用基础数组结构，在单次遍历（o(n)）时间复杂度内高效定位数组中最大值的全部重复出现位置，纠正关于“双循环必为 o(n²)”的常见误解。
本文介绍如何仅使用基础数组结构，在单次遍历（o(n)）时间复杂度内高效定位数组中最大值的全部重复出现位置，纠正关于“双循环必为 o(n²)”的常见误解。
在算法设计中，时间复杂度分析常因对循环结构的理解偏差而误判。一个典型误区是：看到“两次独立遍历数组”，便错误推导为 O(n) × O(n) = O(n²)。实际上，顺序执行的两个线性扫描仍是线性时间——即 O(n) + O(n) = O(2n) = O(n)。这一原理完全适用于本题：仅用原生数组、不借助哈希表或额外高级数据结构，即可在 O(n) 时间内准确找出所有最大值的重复项。
核心思路：两遍扫描，一次定最大，一次数重复
- 第一遍扫描（找全局最大值）：遍历整个数组，记录 maxVal；
- 第二遍扫描（统计最大值出现次数及位置）：再次遍历，对每个等于 maxVal 的元素进行计数或记录索引。
该方案无需嵌套循环，空间复杂度仅为 O(1)（若仅需计数）或 O(k)（k 为重复次数，用于存索引），严格满足“仅用数组”的约束。
以下是简洁、可运行的示例代码（Java）：
public static int[] findMaxDuplicates(int[] arr) {
if (arr == null || arr.length == 0) return new int[0];
// Step 1: Find maximum value — O(n)
int maxVal = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > maxVal) maxVal = arr[i];
}
// Step 2: Collect all indices where maxVal occurs — O(n)
java.util.List<Integer> indices = new java.util.ArrayList<>();
for (int i = 0; i < arr.length; i++) {
if (arr[i] == maxVal) indices.add(i);
}
// Convert to array (optional)
return indices.stream().mapToInt(Integer::intValue).toArray();
}✅ 调用示例：findMaxDuplicates(new int[]{3, 7, 2, 7, 1, 7}) → 返回 [1, 3, 5]（0-based 索引）
关键澄清与注意事项
❌ 错误认知：“两个 for 循环 = 嵌套 = O(n²)”
✅ 正确认知：“两个并列 for 循环 = 串行执行 = O(n) + O(n) = O(n)”可进一步优化为单遍扫描（一次完成最大值发现与重复统计），但逻辑稍复杂，且不改变渐进时间复杂度：仍为 O(n)，常数因子略小，但可读性下降。对于教学与工程实践，清晰分离职责的两遍方案更推荐。
若题目仅要求“判断是否存在重复最大值”（布尔结果），可在第一遍扫描中维护 countMax 和 maxVal，边更新边计数，实现真正单遍 O(n) ——但本题目标是“找出所有重复项”，故需显式收集位置，两遍更自然、鲁棒。
总结
仅依赖基础数组时，求最大值的所有重复项是一个典型的 O(n) 问题，其最优解无需任何辅助数据结构。正确理解“顺序执行 ≠ 嵌套执行”是避免时间复杂度误判的关键。坚持分步思维（先求极值，再查匹配），既保证正确性，又兼顾代码可维护性与性能最优性。
