如何在 O(n) 时间内高效找出数组中所有重复元素（避免重复添加）-java教程-PHP中文网

如何在 O(n) 时间内高效找出数组中所有重复元素（避免重复添加）

本教程讲解如何在线性时间内找出 0 到 n−1 范围内整数数组中的所有重复元素，严格去重并升序返回；重点解析原地标记法的原理、实现与边界处理，规避排序+嵌套循环导致的重复录入和超时问题。

本教程讲解如何在线性时间内找出 0 到 n−1 范围内整数数组中的所有重复元素，严格去重并升序返回；重点解析原地标记法的原理、实现与边界处理，规避排序+嵌套循环导致的重复录入和超时问题。

在解决“查找数组中重复元素”这类问题时，一个常见误区是先排序再遍历比对——虽然逻辑直观，但会带来两个严重问题：一是时间复杂度退化为 O(N log N)，不满足题目要求的 O(N)；二是重复元素连续出现时（如 [1,1,1]），内层循环会导致同一重复值被多次加入结果列表（如输出 1,1 而非仅 1）。你提供的代码正是如此：arr = [1,1,1] 时，i=0 匹配 j=1 和 j=2，两次添加 1，造成结果重复。

✅ 正确解法应遵循两大约束：

时间 O(N)：不能依赖排序或双重循环；
空间 O(1) 辅助空间（除返回列表外）：禁止使用 HashSet 或额外计数数组。

? 核心思路：利用数组下标与值的映射关系进行原地标记
由于题目限定 arr[i] ∈ [0, N−1]，每个元素值都可作为合法下标。我们可通过修改 arr[arr[i] % n] 的值来标记该数字是否已出现过——例如，将首次访问的 val 对应位置 arr[val] 加上 n（即 arr[val] += n），后续再次遇到 val 时，若发现 arr[val] ≥ 2n，即可判定其为重复元素。

⚠️ 注意：因数组可能含重复值，直接取 arr[k] 可能已被修改，故统一用 k % n 获取原始值（确保下标安全）。

以下是符合要求的完整实现：

import java.util.*;

class Solution {
    public static ArrayList<integer> duplicates(int arr[], int n) {
        ArrayList<integer> result = new ArrayList();
        final int marker = n; // 用 n 作为增量标记基数

        // 第一遍扫描：对每个值 val = arr[i]，标记 arr[val % n] += n
        for (int i = 0; i = 2 * marker) {
                result.add(i);
            }
        }

        // 若无重复，返回 [-1]
        if (result.isEmpty()) {
            result.add(-1);
        }

        return result;
    }
}</integer></integer>

? 关键点解析：

为什么加 n？ 因为所有原始值 ∈ [0, n−1]，加 n 后必然 ≥ n，且 arr[i] ≥ 2n 是“至少出现两次”的充要条件（一次标记 + 至少一次再访问）；
为何用 arr[i] % n？ 确保无论 arr[i] 是否已被修改（如变成 n+3），% n 总能还原出原始值 3，保障下标正确性；
为何结果天然升序？ 第二遍按 i = 0 到 n−1 遍历下标，添加顺序即数值升序，无需额外排序。