Java集合实现移除单个重复元素后返回剩余重复项问题

需要实现一个Java方法returnDuplicate，功能是接收一个Integer数组，找出所有重复元素，返回移除每个重复元素中一个实例后的结果。例如输入数组{1,1,2,2,2}，应返回{1,2,2}（即每个元素保留「重复次数-1」个实例）。

当前编写的方法返回结果不符合预期，比如输入上述示例时返回{1,2}，需要修复。

方法定义 #

public static Integer[] returnDuplicate (Integer[] list ){
        // Insert your code here. You may want to change the return value. 
    
        return null;
}

现有代码 #

public static Integer[] returnDuplicate (Integer[] list ){
        List<Integer> uniqueList = new ArrayList<Integer>();
        for (int k = 0; k < list.length; k++) {
                  for (int j = 0; j < list.length; j++) {
                       if (list[k] == list[j] && k != j && !uniqueList.contains(list[k])) {
                uniqueList.add(list[k]);
            }
                   }
        }
        Integer[] result = new Integer[uniqueList.size()];
        int i = 0;
        for (Integer val : uniqueList) {
            result[i++] = val;
        }
        return result;
        
}

问题分析 #

现有代码的逻辑是仅收集每个重复元素一次，完全忽略了元素的重复次数，所以最终结果里每个重复元素只出现一次，无法满足「保留重复次数-1个实例」的要求。

修复方案 #

方案一：统计元素出现次数后生成结果（高效，顺序不保证） #

通过HashMap统计每个元素的出现次数，再根据次数生成对应数量的元素：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class DuplicateProcessor {
    public static Integer[] returnDuplicate(Integer[] list) {
        // 统计每个元素的出现次数
        Map<Integer, Integer> countMap = new HashMap<>();
        for (Integer num : list) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }

        // 生成结果：每个重复元素添加（次数-1）次
        List<Integer> resultList = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
            int repeatCount = entry.getValue();
            if (repeatCount > 1) {
                for (int i = 0; i < repeatCount - 1; i++) {
                    resultList.add(entry.getKey());
                }
            }
        }

        return resultList.toArray(new Integer[0]);
    }
}

方案二：保留原数组顺序的实现（优化版，时间复杂度O(n)） #

如果需要严格保留原数组中重复元素的出现顺序，可先统计总次数，再遍历原数组生成结果：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class DuplicateProcessor {
    public static Integer[] returnDuplicate(Integer[] list) {
        // 提前统计所有元素的总出现次数
        Map<Integer, Integer> totalCountMap = new HashMap<>();
        for (Integer num : list) {
            totalCountMap.put(num, totalCountMap.getOrDefault(num, 0) + 1);
        }

        Map<Integer, Integer> addedCount = new HashMap<>();
        List<Integer> resultList = new ArrayList<>();

        for (Integer num : list) {
            int currentAdded = addedCount.getOrDefault(num, 0);
            int needAdd = totalCountMap.get(num) - 1;
            // 当已添加数量小于需要保留的数量时，加入结果
            if (currentAdded < needAdd) {
                resultList.add(num);
                addedCount.put(num, currentAdded + 1);
            }
        }

        return resultList.toArray(new Integer[0]);
    }
}

效果验证 #

• 输入{1,1,2,2,2}时，两个方案均返回[1,2,2]；
• 输入{1,2,1,2,2}时，方案一返回[1,1,2,2]（顺序取决于HashMap），方案二返回[1,2,2]（和原数组中重复元素的出现顺序一致）。

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