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

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;
    }

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

Answer 1

我建议您从计算某个项目在 List 中出现的次数的方法入手。像

private static <T> int count(List<T> al, T val) {
    int r = 0;
    for (T t : al) {
        if (t.equals(val)) {
            r++;
        }
    }
    return r;
}

然后创建一个新的 List 到 return，并检查 count 是否为 1，然后再将其添加到 List，例如

private static List<Integer> getUniques(List<Integer> list) {
    List<Integer> al = new ArrayList<>();
    for (Integer n : list) {
        if (count(list, n) == 1) {
            al.add(n);
        }
    }
    return al;
}

Answer 2

更好的方法是使用 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;
}

Answer 3

使用 Java 8，您可以使用流 API 执行 Mshnik 正在执行的操作。但是，由于这仍然是一个新的 API，您可能需要在工作中谨慎使用它。可读性（你和你的同行）应该胜过简洁。如果使用 Java 8/stream API 不是一个选项，那么我会选择 Mshnik 的解决方案。

List<Integer> uniques = 
    list.stream().
         collect(Collectors.groupingBy(i -> i, Collectors.reducing(0, (a, b) -> a + b))). //Adding all occurances of that number {3->6, 5->5, 8->16, 2->2}
         entrySet().stream(). //The above map's entries as a set
         filter(e -> e.getValue() == e.getKey()). //Retains {5->5, 2->2}
         map(e -> e.getKey()). //Retains {5, 2}
         collect(Collectors.<Integer>toList()); //Collects

请注意，虽然每一行看起来都是列表的另一次迭代，但这实际上是一个 2 遍解决方案（第一遍是当我们收集 map 时，第二遍是当我们收集列表时）。

复杂度：预期 O(N) -- 因为 groupingBy 将使用 HashMap。

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

Removing all non-unique members of a list

java

loops

exception-handling

exception

concurrentmodification