如果列表中的项目多次出现，则删除该项目的所有实例

提问者：小点点

如果列表中的项目多次出现，则删除该项目的所有实例

给定一个数字列表:{4，5，7，3，5，4，2，4}

所需的输出为:{7，3，2}

我正在考虑的解决方案是从给定的列表中创建下面的HashMap:

Map<Integer, Integer> numbersCountMap = new HashMap();

其中key是列表中的值，value是出现次数。

然后循环遍历HashMap条目集，并在该数字包含大于1的计数时，从列表中删除该数字。

for (Map.Entry<Int, Int> numberCountEntry : numbersCountMap.entrySet()) {
     if(numberCountEntry.getValue() > 1) {  
        testList.remove(numberCountEntry.getKey());
     }
}

我不确定这是否是解决此问题的有效方案，因为列表上的remove(Integer)操作可能会很昂贵。此外，我正在创建额外的地图数据结构。和循环两次，一次在原始列表上创建映射，然后在映射上删除重复项。

你能不能建议一个更好的方法。可能是Java 8号有更好的方式来实现这一点。我们还能在Java 8中用溪流和其他新的结构在几行中完成吗？

共3个答案

匿名用户

它只是为了这个问题而过度设计。此外，您的代码也有问题:

它是integer，而不是int（小插曲）
更重要的是，remove调用删除第一个匹配的元素，更糟糕的是，列表上的remove被重载:有remove(int)通过索引删除元素，还有remove(Object)通过查找删除元素。在列表中，很难知道要调用的是哪一个。您需要“按查找删除”。

关于复杂性:

在现代CPU上，这就没那么简单了。 CPU在内存的“页面”上工作，因为获取一个新的页面大约需要500个周期或更多，所以简化问题，考虑任何不需要加载新的内存页面的操作都是即时的，这是更有意义的。

这意味着如果我们讨论的是一个列表，比如说，一万个数字或者更少？都无关紧要。它会飞过的。任何关于“效率”的争论都是没有意义的，除非我们讨论到更大的问题。

假设“效率”仍然相关:

整数没有哈希代码冲突。
在所有单元素操作（如“add”和“get”）上，很少或没有键哈希冲突的哈希映射实际上是O(1)。
ArrayList的。Remove（Object）方法为O(n)。清单越大，花费的时间越长。实际上，它是加倍的O(n):需要O(n)时间来找到你想要移除的元素，然后又需要O(n)时间来实际移除它。对于基础信息学，两次O(n)仍然是O(n)，但从实用角度讲，arraylist.remove（item)是昂贵的。
您正在调用。删除大约O(n)次，使总复杂度为O(n^2)。不是很好，也不是最有效的算法。实际上或根本上。

一个有效的策略可能是仅仅致力于复制。复制操作为O(n)。而不是每个项目的O(n)。排序为O（n log n）。这给了我们一个微不足道的算法:

对输入进行排序。请注意，您也可以使用int[]来完成此操作；在Java 16问世并且可以在集合中使用原语之前，int[]比list的效率高一个数量级。
遍历排序后的输入。不要立即复制，而是使用一个中间词:对于列表中的第0个条目，只记得'the last item was foo'和'How mo times did I see foo？‘。然后，对于任何一项，检查它是否与前面的相同。如果是，则递增计数。如果不是，则检查计数:如果是1，则将其添加到输出中，否则不添加。在任何情况下，都要将“最后看到的值”更新为新值，并将计数设置为1。最后，如果计数为1，请确保添加上次记住的值，并确保您的代码即使对于空列表也能工作。

这是O(n^2)+O(n)的复杂性，它是O(n^2)，比您的O(n^2)要好得多。

使用int[]，并添加另一个步骤，首先通过juuust来计算输出的大小（因为数组不能增长/收缩），现在您的时间复杂度为O(nlogn)+2*O(n)，它仍然是O(nlogn)，并且内存复杂度最低，因为排序已经到位，而且不需要额外的开销。

如果你真的想调整它，你可以使用0的空间复杂度（你可以在输入里面写精简的列表）。

这种策略的一个问题是，您会把输入中的顺序搞乱。该算法将生成2，3，7。如果希望保持顺序，可以将hashmap解决方案与sort结合起来，并在循环解决方案时制作一个副本。

匿名用户

您可以在LinkedHashMap中计算每个数字的频率，以便在相关的情况下保持插入顺序，然后从entrySet()中筛选出单个数字并保留键。

List<Integer> data = Arrays.asList(4, 5, 7, 3, 5, 4, 2, 4);
List<Integer> singles = data.stream()
    .collect(Collectors.groupingBy(Function.identity(), LinkedHashMap::new, Collectors.counting()))
    .entrySet().stream()
    .filter(e -> e.getValue() == 1)
    .map(Map.Entry::getKey)
    .collect(Collectors.toList());

System.out.println(singles);

打印输出:

[7, 3, 2]

匿名用户

按您可以使用的流:

Map<Integer, Long> grouping = integers.stream()
        .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
grouping.values().removeIf(c -> c > 1);
Set<Integer> result = grouping.keySet();

或者就像@Holger提到的，你只想知道你的列表中是否有一个以上的整数，所以只要做:

Map<Integer, Boolean> grouping = integers.stream()
        .collect(Collectors.toMap(Function.identity(),
                x -> false, (a, b) -> true,
                HashMap::new));
grouping.values().removeIf(b -> b);
// or
grouping.values().removeAll(Collections.singleton(true));
Set<Integer> result = grouping.keySet();