O(n)数组找最大值重复项技巧

本文揭示了一个常被误解的算法真相：仅用基础数组结构，通过两次独立的线性扫描（而非嵌套循环），就能在严格 O(n) 时间复杂度内精准找出数组中最大值的所有重复出现位置——既纠正了“双循环必为 O(n²)”的认知误区，又展示了时间复杂度分析中“顺序执行叠加仍为线性”的核心原理；方法简洁高效、无需哈希表等额外数据结构，兼具教学清晰性与工程实用性，让你用最朴素的工具，做出最扎实的性能保证。

本文介绍如何仅使用基础数组结构，在单次遍历（O(n)）时间复杂度内高效定位数组中最大值的全部重复出现位置，纠正关于“双循环必为 O(n²)”的常见误解。

本文介绍如何仅使用基础数组结构，在单次遍历（O(n)）时间复杂度内高效定位数组中最大值的全部重复出现位置，纠正关于“双循环必为 O(n²)”的常见误解。

在算法设计中，时间复杂度分析常因对循环结构的理解偏差而误判。一个典型误区是：看到“两次独立遍历数组”，便错误推导为 O(n) × O(n) = O(n²)。实际上，顺序执行的两个线性扫描仍是线性时间——即 O(n) + O(n) = O(2n) = O(n)。这一原理完全适用于本题：仅用原生数组、不借助哈希表或额外高级数据结构，即可在 O(n) 时间内准确找出所有最大值的重复项。

核心思路：两遍扫描，一次定最大，一次数重复

1. 第一遍扫描（找全局最大值）：遍历整个数组，记录 maxVal；
2. 第二遍扫描（统计最大值出现次数及位置）：再次遍历，对每个等于 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) 问题，其最优解无需任何辅助数据结构。正确理解“顺序执行 ≠ 嵌套执行”是避免时间复杂度误判的关键。坚持分步思维（先求极值，再查匹配），既保证正确性，又兼顾代码可维护性与性能最优性。

今天关于《O(n)数组找最大值重复项技巧》的内容就介绍到这里了，是不是学起来一目了然！想要了解更多关于的内容请关注golang学习网公众号！