java - 删除列表中的所有非唯一成员

Question

我想创建一个方法来过滤掉列表中所有非唯一成员，例如带有输入的列表

3 5 3 8 8 2

会变成

5 2

我有尝试以下方法的想法:

private static List<Integer> getUniques(List<Integer> list) {
        for (Integer n : list) {
            list.remove(n);
            if (!list.contains(n)) {
                list.add(n);
            } else {
                while (list.contains(n)) {
                    list.remove(n);
                }
            }
        }
        return list;
    }

但这会引发并发修改异常。我做了一个工作调整:

private static List<Integer> getUniques(List<Integer> list) {
        List<Integer> result = new ArrayList<>();
        Set<Integer> distinctSet = new HashSet<>();

        distinctSet.addAll(list);
        result.addAll(list);

        for (Integer n : distinctSet) {
            result.remove(n);
            if (!result.contains(n)) {
                result.add(n);
            } else {
                while (result.contains(n)) {
                    result.remove(n);
                }
            }
        }
        return result;
    }

这实现了我想要的，但似乎有点复杂/低效。有没有办法让我按照我想到的第一种方式去做？或者一般来说另一种更有效的方法？或者我基本上已经使用了可用的最佳方法？

Answer 1

更好的方法是使用 HashMap 来标记要保留的元素，然后基于该元素进行添加。此方法的复杂度为 O(N)，比您的解决方案的 O(N^2) 更好(删除可能为 O(N) >，取决于传入的 List 实现)。如果这很重要的话，它当然也保留了原始列表中元素的顺序。

private static List<Integer> getUniques(List<Integer> list) {
    HashMap<Integer, Boolean> flagMap = new HashMap<>();

    //Total Loop: O(N)
    for(Integer i : list){
        if(flagMap.containsKey(i)) flagMap.put(i, false); //O(1)
        else flagMap.put(i, true); //O(1)
    }

    ArrayList<Integer> result = new ArrayList<Integer>();

    //Total Loop: O(N)
    for(Integer i : list){
        if(flagMap.get(i)) result.add(i); //O(1)
    }
    return result;
}