数组重复元素查找：如何让结果中重复元素仅出现一次？

你的代码存在两个关键问题：

• 时间复杂度不达标：双重嵌套循环加上Arrays.sort(arr)的组合，时间复杂度为O(n log n + n²)，面对n=10^5的测试用例会直接超时。
• 重复元素多次录入：只要检测到arr[i]==arr[j]就往列表中添加元素，导致同一个重复值被多次记录（比如输入中的25出现3次，就被添加了3次）。

符合要求的修正方案（O(n)时间 + 原数组操作） #

利用题目中元素取值范围为0到n-1的约束，我们可以直接在原数组上通过标记元素符号的方式识别重复元素，实现线性时间复杂度，同时避免额外的大空间开销：

import java.util.ArrayList;
import java.util.Collections;

class Solution {
    public static ArrayList<Integer> duplicates(int arr[], int n) {
        ArrayList<Integer> result = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            // 取当前元素的绝对值作为索引（因为可能已经被标记为负数）
            int idx = Math.abs(arr[i]);
            
            // 如果对应索引的元素为负，说明当前数之前已经出现过
            if (arr[idx] < 0) {
                // 去重：仅当结果列表中未包含该数时才添加
                if (!result.contains(idx)) {
                    result.add(idx);
                }
            } else {
                // 第一次遇到该数，将对应索引的元素标记为负数
                arr[idx] = -arr[idx];
            }
        }
        
        // 处理无重复元素的情况
        if (result.isEmpty()) {
            result.add(-1);
        } else {
            // 题目要求返回升序列表，对结果排序（排序复杂度为O(k log k)，k远小于n）
            Collections.sort(result);
        }
        
        return result;
    }
}

代码说明 #

1. 标记逻辑：每个元素的值都可以作为数组的合法索引，第一次遇到某个数时，将对应索引的元素转为负数做标记；第二次遇到时，发现对应索引元素为负，即可判定为重复元素。
2. 去重处理：通过!result.contains(idx)判断，避免同一个重复元素被多次录入结果列表。
3. 排序收尾：由于标记过程是按原数组顺序遍历，结果列表是无序的，最后排序以满足题目要求的升序输出，这一步的时间开销可以忽略不计。

基于排序思路的临时修复（仅解决重复录入，不满足O(n)时间） #

如果暂时想基于你原有的排序思路修改，也可以解决重复录入问题，但时间复杂度为O(n log n)（排序的时间开销），不符合题目要求的线性时间：

import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    public static ArrayList<Integer> duplicates(int arr[], int n) {
        ArrayList<Integer> list1 = new ArrayList<>();
        Arrays.sort(arr);
        
        for (int i = 0; i < n - 1; i++) {
            // 检测到连续重复元素
            if (arr[i] == arr[i+1]) {
                // 仅当列表为空，或最后一个元素不等于当前元素时添加（去重）
                if (list1.isEmpty() || list1.get(list1.size()-1) != arr[i]) {
                    list1.add(arr[i]);
                }
                // 跳过所有连续重复的元素，避免重复判断
                while (i < n-1 && arr[i] == arr[i+1]) {
                    i++;
                }
            }
        }
        
        if (list1.isEmpty()) {
            list1.add(-1);
        }
        return list1;
    }
}

内容的提问来源于stack exchange，提问作者Vaishali Sharma