Java 8, Streams untuk menemukan elemen duplikat

87

Saya mencoba untuk membuat daftar elemen duplikat dalam daftar integer katakan misalnya,

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

menggunakan Streams of jdk 8. Ada yang sudah mencobanya. Untuk menghapus duplikat kita bisa menggunakan api yang berbeda (). Tapi bagaimana dengan menemukan elemen duplikat? Ada yang bisa membantu saya?

Siva
sumber
Jika Anda tidak ingin mengumpulkan aliran, intinya adalah "bagaimana saya bisa melihat lebih dari satu item sekaligus dalam aliran"?
Thorbjørn Ravn Andersen
Setel <Integer> items = new HashSet (); number.stream (). filter (n -> i! tems.add (n)). collect (Collectors.toSet ());
Saroj Kumar Sahoo

Jawaban:

127

Anda dapat menggunakan Collections.frequency:

numbers.stream().filter(i -> Collections.frequency(numbers, i) >1)
                .collect(Collectors.toSet()).forEach(System.out::println);
Bao Dinh
sumber
11
Performa O (n ^ 2) yang sama seperti pada jawaban @OussamaZoghlami , meski mungkin lebih sederhana. Namun demikian, inilah suara positifnya. Selamat datang di StackOverflow!
Tagir Valeev
6
Seperti disebutkan, ini adalah solusi ^ 2 di mana ada solusi linier trivial. Saya tidak akan menerima ini di CR.
jwilner
3
Ini mungkin lebih lambat daripada opsi @Dave, tapi ini lebih cantik jadi saya akan menerima performa terbaiknya.
jDub9
@jwilner adalah maksud Anda mengenai solusi n ^ 2 yang mengacu pada penggunaan Collections.frequency dalam filter?
mancocapac
5
@mancocapac ya, ini kuadrat karena panggilan frekuensi harus mengunjungi setiap elemen dalam angka, dan dipanggil pada setiap elemen. Jadi, untuk setiap elemen, kami mengunjungi setiap elemen - n ^ 2 dan tidak perlu tidak efisien.
jwilner
72

Contoh dasar. Bagian pertama membuat peta frekuensi, bagian kedua menguranginya menjadi daftar yang difilter. Mungkin tidak seefisien jawaban Dave, tetapi lebih fleksibel (seperti jika Anda ingin mendeteksi tepat dua, dll.)

     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() );
RobAu
sumber
12
Jawaban ini adalah benar karena bersifat linier dan tidak melanggar aturan "stateless predicate".
jwilner
55

Anda memerlukan satu set (di allItemsbawah) untuk menampung seluruh konten array, tetapi ini adalah 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
sumber
18
filter()membutuhkan predikat tanpa kewarganegaraan. "Solusi" Anda sangat mirip dengan contoh predikat stateful yang diberikan di javadoc: docs.oracle.com/javase/8/docs/api/java/util/stream/…
Matt McHenry
1
@MattMcHenry: apakah itu berarti solusi ini berpotensi menghasilkan perilaku yang tidak terduga, atau ini hanya praktik yang buruk?
IcedDante
7
@IcedDante Dalam kasus lokal seperti di mana Anda tahu pasti bahwa streaming sequential(), mungkin aman. Dalam kasus yang lebih umum di mana streaming mungkin terjadi parallel(), dijamin akan rusak dengan cara yang aneh.
Matt McHenry
5
Selain menghasilkan perilaku tak terduga dalam beberapa situasi, ini mencampurkan paradigma seperti yang menurut Bloch, Anda tidak boleh melakukannya di edisi ketiga Java Efektif. Jika Anda menemukan diri Anda menulis ini, gunakan saja for loop.
jwilner
6
Menemukan ini di alam liar digunakan oleh kendala Hibernate Validator UniqueElements .
Dave
14

Cara O (n) adalah seperti di bawah ini:

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());

Kompleksitas ruang akan berlipat ganda dalam pendekatan ini, tetapi ruang itu tidak sia-sia; pada kenyataannya, kita sekarang memiliki duplikatnya saja sebagai satu Set dan juga Set lain dengan semua duplikatnya juga dihapus.

Thomas Mathew
sumber
13

Perpustakaan StreamEx saya yang meningkatkan aliran Java 8 menyediakan operasi khusus distinct(atLeast)yang hanya dapat mempertahankan elemen yang muncul setidaknya dalam jumlah yang ditentukan. Jadi masalah Anda bisa diselesaikan seperti ini:

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

Secara internal, ini mirip dengan solusi @Dave, ini menghitung objek, untuk mendukung jumlah lain yang diinginkan dan cocok untuk paralel (digunakan ConcurrentHashMapuntuk aliran paralel, tetapi HashMapuntuk sekuensial). Untuk data dalam jumlah besar, Anda dapat mempercepat penggunaan .parallel().distinct(2).

Tagir Valeev
sumber
26
Pertanyaannya adalah tentang Java Streams, bukan pustaka pihak ketiga.
ᄂ ᄀ
9

Anda bisa mendapatkan duplikatnya seperti ini:

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
sumber
11
Bukankah itu operasi O (n ^ 2)?
Trejkaz
4
Coba gunakannumbers = Arrays.asList(400, 400, 500, 500);
Tagir Valeev
1
Apakah ini mirip dengan membuat loop 2 kedalaman? untuk (..) {untuk (..)} Hanya ingin tahu cara kerjanya secara internal
redigaffi
Meskipun ini adalah pendekatan yang bagus, namun memiliki streambagian dalam streamitu mahal.
Vishwa Ratna
4

Saya pikir solusi dasar untuk pertanyaan tersebut harus seperti di bawah ini:

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());

baik, tidak disarankan untuk melakukan operasi filter, tetapi untuk pemahaman yang lebih baik, saya telah menggunakannya, terlebih lagi, harus ada beberapa penyaringan khusus di versi mendatang.

Prashant
sumber
3

Multiset adalah struktur yang mempertahankan jumlah kemunculan untuk setiap elemen. Menggunakan implementasi Guava:

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

pembuatan peta atau aliran tambahan memakan waktu dan ruang…

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]


… Dan untuk pertanyaan yang diklaim sebagai [duplikat]

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
sumber
1

Jika Anda hanya perlu mendeteksi keberadaan duplikat (alih-alih mencantumkannya, yang diinginkan OP), cukup ubah menjadi List dan Set, lalu bandingkan ukurannya:

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

Saya suka pendekatan ini karena lebih sedikit tempat untuk kesalahan.

Patrick
sumber
0

Saya rasa saya punya solusi yang baik bagaimana memperbaiki masalah seperti ini - Daftar => Daftar dengan pengelompokan berdasarkan Sesuatu.a & Sesuatu.b. Ada definisi tambahan:

public class Test {

    public static void test() {

        class A {
            private int a;
            private int b;
            private float c;
            private float d;

            public A(int a, int b, float c, float d) {
                this.a = a;
                this.b = b;
                this.c = c;
                this.d = d;
            }
        }


        List<A> list1 = new ArrayList<A>();

        list1.addAll(Arrays.asList(new A(1, 2, 3, 4),
                new A(2, 3, 4, 5),
                new A(1, 2, 3, 4),
                new A(2, 3, 4, 5),
                new A(1, 2, 3, 4)));

        Map<Integer, A> map = list1.stream()
                .collect(HashMap::new, (m, v) -> m.put(
                        Objects.hash(v.a, v.b, v.c, v.d), v),
                        HashMap::putAll);

        list1.clear();
        list1.addAll(map.values());

        System.out.println(list1);
    }

}

kelas A, list1 itu hanya data yang masuk - sihir ada di Objects.hash (...) :)

Zhurov Konstantin
sumber
1
Peringatan: Jika Objects.hashmenghasilkan nilai yang sama untuk (v.a_1, v.b_1, v.c_1, v.d_1)dan (v.a_2, v.b_2, v.c_2, v.d_2), maka mereka akan dianggap sama dan dihapus sebagai duplikat, tanpa benar-benar memeriksa bahwa a, b, c, dan d adalah sama. Ini mungkin risiko yang dapat diterima, atau Anda mungkin ingin menggunakan fungsi selain Objects.hashyang dijamin untuk memberikan hasil yang unik di seluruh domain Anda.
Marty Neal
0

Apakah Anda harus menggunakan idiom java 8 (kuk)? Mungkin solusi sederhana akan memindahkan kompleksitas ke peta seperti struktur data yang menyimpan angka sebagai kunci (tanpa pengulangan) dan waktu muncul sebagai nilai. Anda dapat mengulangi peta itu dan hanya melakukan sesuatu dengan angka-angka yang ocurrs> 1.

import java.lang.Math;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.HashMap;
import java.util.Iterator;

public class RemoveDuplicates
{
  public static void main(String[] args)
  {
   List<Integer> numbers = Arrays.asList(new Integer[]{1,2,1,3,4,4});
   Map<Integer,Integer> countByNumber = new HashMap<Integer,Integer>();
   for(Integer n:numbers)
   {
     Integer count = countByNumber.get(n);
     if (count != null) {
       countByNumber.put(n,count + 1);
     } else {
       countByNumber.put(n,1);
     }
   }
   System.out.println(countByNumber);
   Iterator it = countByNumber.entrySet().iterator();
    while (it.hasNext()) {
        Map.Entry pair = (Map.Entry)it.next();
        System.out.println(pair.getKey() + " = " + pair.getValue());
    }
  }
}
Pemenang
sumber
0

Coba solusi ini:

public class Anagramm {

public static boolean isAnagramLetters(String word, String anagramm) {
    if (anagramm.isEmpty()) {
        return false;
    }

    Map<Character, Integer> mapExistString = CharCountMap(word);
    Map<Character, Integer> mapCheckString = CharCountMap(anagramm);
    return enoughLetters(mapExistString, mapCheckString);
}

private static Map<Character, Integer> CharCountMap(String chars) {
    HashMap<Character, Integer> charCountMap = new HashMap<Character, Integer>();
    for (char c : chars.toCharArray()) {
        if (charCountMap.containsKey(c)) {
            charCountMap.put(c, charCountMap.get(c) + 1);
        } else {
            charCountMap.put(c, 1);
        }
    }
    return charCountMap;
}

static boolean enoughLetters(Map<Character, Integer> mapExistString, Map<Character,Integer> mapCheckString) {
    for( Entry<Character, Integer> e : mapCheckString.entrySet() ) {
        Character letter = e.getKey();
        Integer available = mapExistString.get(letter);
        if (available == null || e.getValue() > available) return false;
    }
    return true;
}

}
Ilia Galperin
sumber
0

Bagaimana dengan pemeriksaan indeks?

        numbers.stream()
            .filter(integer -> numbers.indexOf(integer) != numbers.lastIndexOf(integer))
            .collect(Collectors.toSet())
            .forEach(System.out::println);
bagom
sumber
1
Seharusnya berfungsi dengan baik, tetapi juga kinerja O (n ^ 2) sebagai beberapa solusi lain di sini.
Florian Albrecht