Java 8，使用Streams查找重复元素

Question

我试图列出整数列表中重复的元素，例如：

List<Integer> numbers = Arrays.asList(new Integer[]{1,2,1,3,4,4});    

使用JDK 8的Streams功能。有人尝试过吗？为了删除重复元素，我们可以使用distinct() API。但是如果想要查找重复的元素呢？有人能帮我吗？

- Siva

---

可能是使用分组、计数和过滤操作收集流的重复问题。 - Tagir Valeev

如果您不想收集流，则本质上可以归结为“如何在流中同时查看多个项目”？ - Thorbjørn Ravn Andersen

Set<Integer> items = new HashSet(); numbers.stream().filter(n -> !items.add(n)).collect(Collectors.toSet()); - Saroj Kumar Sahoo

Answer 1

你可以使用Collections.frequency方法：

numbers.stream().filter(i -> Collections.frequency(numbers, i) >1)
                .collect(Collectors.toSet()).forEach(System.out::println);

- Bao Dinh

---

和@OussamaZoghlami的回答一样，时间复杂度为O(n^2)，尽管这个方法可能更简单。不过我还是给你点了赞。欢迎来到StackOverflow! - Tagir Valeev

如前所述，这是一个n^2的解决方案，而存在一个简单的线性解决方案。我不会在评审中接受这种方法。 - jwilner

可能比起 @Dave 的选项会慢一些，但是它更漂亮，所以我愿意承受性能上的损失。 - wheeleruniverse

@jwilner提到的n^2解决方案是指在过滤器中使用Collections.frequency吗？ - mancocapac

@mancocapac 是的，它是二次的，因为频率调用必须访问numbers中的每个元素，并且对于每个元素都被调用一次。因此，对于每个元素，我们都要访问每个元素 -- n^2，非常低效。 - jwilner

Answer 2

基本示例。前半部分构建频率映射，后半部分将其缩减为过滤列表。可能不像Dave的回答那样高效，但更加通用（例如，如果您想要检测确切的两个等）。

List<Integer> duplicates = IntStream.of( 1, 2, 3, 2, 1, 2, 3, 4, 2, 2, 2 )
   .boxed()
   .collect( Collectors.groupingBy( Function.identity(), Collectors.counting() ) )
   .entrySet()
   .stream()
   .filter( p -> p.getValue() > 1 )
   .map( Map.Entry::getKey )
   .collect( Collectors.toList() );

- Rob Audenaerde

---

我认为这个答案是正确的，因为它是线性的，不违反“无状态谓词”的规则。 - jwilner

@jwilner，这并不是真的，“Collectors.counting（）”与上面的答案相同。在我看来，在一个小集合中，上面的方法更简单、更清晰。 - kidnan1991

@kidnan1991 这不一样。在上面的答案中，每个项目都会根据其频率进行过滤，然后再针对每个项目进行处理。这与制作地图真的是完全不同的事情。 - Rob Audenaerde

Answer 3

你需要一个集合（下面是allItems），来保存整个数组的内容，但这是O(n)：

Integer[] numbers = new Integer[] { 1, 2, 1, 3, 4, 4 };
Set<Integer> allItems = new HashSet<>();
Set<Integer> duplicates = Arrays.stream(numbers)
        .filter(n -> !allItems.add(n)) //Set.add() returns false if the item was already in the set.
        .collect(Collectors.toSet());
System.out.println(duplicates); // [1, 4]

- Dave

---

filter()需要一个无状态谓词。你提供的“解决方案”与Java文档中给出的有状态谓词示例非常相似。参考链接：https://docs.oracle.com/javase/8/docs/api/java/util/stream/package-summary.html#Statelessness - Matt McHenry

@MattMcHenry：这是否意味着该解决方案有可能产生意外行为，还是只是不良实践？ - IcedDante

在像这种本地化的情况下，你可以确定流是sequential()时，这很可能是安全的。在更一般的情况下，流可能是parallel()，那么很有可能会出现奇怪的错误。 - Matt McHenry

除了在某些情况下产生意外行为之外，这种方法还混合了范式，正如Bloch在《Effective Java》第三版中所说的那样，不应该这样做。如果你发现自己正在写这种代码，请使用for循环代替。 - jwilner

在野外发现了Hibernate Validator中使用的UniqueElements约束。 - Dave

Answer 4

一种O(n)的方法如下：

List<Integer> numbers = Arrays.asList(1, 2, 1, 3, 4, 4);
Set<Integer> duplicatedNumbersRemovedSet = new HashSet<>();
Set<Integer> duplicatedNumbersSet = numbers.stream().filter(n -> !duplicatedNumbersRemovedSet.add(n)).collect(Collectors.toSet());

这种方法的空间复杂度会增加一倍，但这些空间并不浪费。实际上，我们现在有一个仅包含副本的Set，以及另一个删除了所有副本的Set。

- Thomas Mathew

---

看起来和上面的Dave的解决方案一样 - https://dev59.com/d14c5IYBdhLWcg3wqLxe#30741906 - AlikElzin-kilaka

Answer 5

我的StreamEx库增强了Java 8流，并提供了一个特殊操作distinct(atLeast)，可以仅保留至少出现指定次数的元素。因此，您可以像这样解决问题：

List<Integer> repeatingNumbers = StreamEx.of(numbers).distinct(2).toList();

在内部，它类似于@Dave的解决方案，它计算对象以支持其他所需的数量，并且它对并行处理友好（它使用ConcurrentHashMap进行并行流处理，但对于顺序处理使用HashMap）。对于大量数据，可以使用.parallel().distinct(2)加速。

- Tagir Valeev

---

问题涉及Java Streams，而非第三方库。 - ﾤ ﾡ

Answer 6

您可以像这样获取重复的内容：

List<Integer> numbers = Arrays.asList(1, 2, 1, 3, 4, 4);
Set<Integer> duplicated = numbers
  .stream()
  .filter(n -> numbers
        .stream()
        .filter(x -> x == n)
        .count() > 1)
   .collect(Collectors.toSet());

- Oussama Zoghlami

---

那不是O(n^2)的操作吗？ - Hakanai

请尝试使用numbers = Arrays.asList(400, 400, 500, 500);。 - Tagir Valeev

这是否类似于创建一个二层循环？for(..) { for(..) } 只是好奇它在内部是如何工作的。 - redigaffi

虽然这是一种不错的方法，但是在stream内部嵌套stream会很昂贵。 - Vishwa Ratna

Answer 7

我认为解决这个问题的基本方法应该如下：

Supplier supplier=HashSet::new; 
HashSet has=ls.stream().collect(Collectors.toCollection(supplier));

List lst = (List) ls.stream().filter(e->Collections.frequency(ls,e)>1).distinct().collect(Collectors.toList());

虽然不推荐进行过滤操作，但为了更好的理解，我已经使用它了。此外，未来版本中应该会有一些自定义过滤功能。

- Prashant

Answer 8

多重集是一种结构，用于维护每个元素的出现次数。使用Guava实现：

Set<Integer> duplicated =
        ImmutableMultiset.copyOf(numbers).entrySet().stream()
                .filter(entry -> entry.getCount() > 1)
                .map(Multiset.Entry::getElement)
                .collect(Collectors.toSet());

- numéro6

Answer 9

如果您只需要检测重复项是否存在（而不是列出它们，这是OP想要的），只需将它们转换为List和Set，然后比较大小：

    List<Integer> list = ...;
    Set<Integer> set = new HashSet<>(list);
    if (list.size() != set.size()) {
      // duplicates detected
    }

我喜欢这种方法，因为它有更少的错误可能性。

- Patrick

Answer 10

创建额外的地图或流是耗费时间和空间的...

最初的回答

Set<Integer> duplicates = numbers.stream().collect( Collectors.collectingAndThen(
  Collectors.groupingBy( Function.identity(), Collectors.counting() ),
  map -> {
    map.values().removeIf( cnt -> cnt < 2 );
    return( map.keySet() );
  } ) );  // [1, 4]

...对于声称是哪个的问题 [重复]

最初的回答

public static int[] getDuplicatesStreamsToArray( int[] input ) {
  return( IntStream.of( input ).boxed().collect( Collectors.collectingAndThen(
      Collectors.groupingBy( Function.identity(), Collectors.counting() ),
      map -> {
        map.values().removeIf( cnt -> cnt < 2 );
        return( map.keySet() );
      } ) ).stream().mapToInt( i -> i ).toArray() );
}

- Kaplan