Java: wykryć duplikaty w ArrayList?


104

Jak mogę zająć się wykrywaniem (zwracaniem prawdy / fałszu), czy ArrayList zawiera więcej niż jeden taki sam element w Javie?

Wielkie dzięki, Terry

Edycja Zapomniałem wspomnieć, że nie chcę porównywać „bloków” ze sobą, ale ich wartości całkowite. Każdy „blok” ma int i to je wyróżnia. Znajduję int określonego bloku, wywołując metodę o nazwie „getNum” (np. Table1 [0] [2] .getNum ();


Jeśli "Block" jest porównywane przez int, prawdopodobnie powinieneś mieć hashCode zwracające to samo int i mieć equals porównuje te int.
Paul Tomblin,

użyj Set zamiast List
dmarquina

Odpowiedzi:


192

Najprostsze: zrzuć całą kolekcję do zestawu (za pomocą konstruktora Set (Collection) lub Set.addAll), a następnie sprawdź, czy zestaw ma taki sam rozmiar jak ArrayList.

List<Integer> list = ...;
Set<Integer> set = new HashSet<Integer>(list);

if(set.size() < list.size()){
    /* There are duplicates */
}

Aktualizacja: Jeśli dobrze rozumiem twoje pytanie, masz 2d tablicę bloków, jak w

Tabela blokowa [] [];

i chcesz sprawdzić, czy któryś z nich ma duplikaty?

W takim przypadku mógłbym wykonać następujące czynności, zakładając, że Block poprawnie implementuje „equals” i „hashCode”:

for (Block[] row : table) {
   Set set = new HashSet<Block>(); 
   for (Block cell : row) {
      set.add(cell);
   }
   if (set.size() < 6) { //has duplicate
   }
}

Nie jestem tego w 100% pewien, jeśli chodzi o składnię, więc bezpieczniej byłoby napisać to jako

for (int i = 0; i < 6; i++) {
   Set set = new HashSet<Block>(); 
   for (int j = 0; j < 6; j++)
    set.add(table[i][j]);
 ...

Set.addzwraca wartość logiczną fałsz, jeśli dodawany element jest już w zestawie, więc możesz nawet zewrzeć i zbalansować każdy dodatek, który powróci, falsejeśli chcesz tylko wiedzieć, czy są jakieś duplikaty.


13
Pamiętaj, aby zaimplementować również hashCode / equals.
jon077

1
Lub nawet trochę prościej: zawiń go podczas tworzenia zestawu, np. New HashSet (lista), zamiast używać addAll.
Fabian Steeg

2
@ jon077: To zależy od twojej definicji „duplikatu”.
Michael Myers

Czy proces wykrywania elementów w tablicy 2D byłby taki sam? Na przykład sprawdzanie z tablicy [0] [0] do tablicy [0] [6] („wiersz”) ..? Wielkie dzięki, Terry

Każdy obiekt w tablicy zawiera wartość całkowitą. Przez „duplikat” obiekt miałby tę samą wartość całkowitą.

60

Ulepszony kod, wykorzystujący zwracaną wartość Set#addzamiast porównywania rozmiaru listy i zestawu.

public static <T> boolean hasDuplicate(Iterable<T> all) {
    Set<T> set = new HashSet<T>();
    // Set#add returns false if the set does not change, which
    // indicates that a duplicate element has been added.
    for (T each: all) if (!set.add(each)) return true;
    return false;
}

7
Byłoby bardziej skuteczne, aby powiedzieć HashSet ile miejsca przeznaczyć: Set<T> set = new HashSet<T>(list.size());? Biorąc pod uwagę parametr listy, myślę, że jest bardziej wydajne, jeśli często lista nie zawiera duplikatów.
Paul Jackson

1
@PaulJackson Dobór na podstawie pełnej listy prawdopodobnie będzie korzystny. Jeśli jednak częstym przypadkiem jest wczesne znajdowanie duplikatu, to miejsce zostało zmarnowane. Również nawet dopasowanie rozmiaru HashSetdo rozmiaru listy spowoduje zmianę rozmiaru podczas przeglądania całej listy ze względu na podstawowy współczynnik ładowania struktury skrótu.
Jay Anderson

1
Jeśli nie wystąpią rzeczywiste problemy ze środowiskiem wykonawczym lub przestrzenią, nie dopracowałbym Twojego kodu w ten sposób. Najlepiej unikać przedwczesnej optymalizacji.
akuhn

15

Jeśli chcesz w ogóle uniknąć duplikatów, powinieneś po prostu odciąć środkowy proces wykrywania duplikatów i użyć zestawu .


1
Upewnij się, że zaimplementowałeś hashCode / equals :)
jon077

@ jon077: Niekoniecznie, jak właśnie powiedziałem.
Michael Myers

1
Jednak użycie zestawu nie wykrywa duplikatów. Po prostu im to zapobiega. O ile oczywiście nie sprawdzisz wyniku metody add, jak wspomniano powyżej przez @akuhn.
mcallahan

13

Ulepszony kod zwracający zduplikowane elementy

  • Potrafi znaleźć duplikaty w kolekcji
  • zwraca zestaw duplikatów
  • Unikalne elementy można zdobyć z zestawu

public static <T> List getDuplicate(Collection<T> list) {

    final List<T> duplicatedObjects = new ArrayList<T>();
    Set<T> set = new HashSet<T>() {
    @Override
    public boolean add(T e) {
        if (contains(e)) {
            duplicatedObjects.add(e);
        }
        return super.add(e);
    }
    };
   for (T t : list) {
        set.add(t);
    }
    return duplicatedObjects;
}


public static <T> boolean hasDuplicate(Collection<T> list) {
    if (getDuplicate(list).isEmpty())
        return false;
    return true;
}

To całkiem niesamowite. masz jakiś nieprawidłowy kod i być może nie jest to najbardziej optymalny sposób, ale Twoje podejście totalnie rządzi! (i działa świetnie)
Jules Colle

9

Jeśli twoje elementy są w jakiś sposób porównywalne (fakt, że kolejność ma jakiekolwiek rzeczywiste znaczenie, jest obojętny - wystarczy, że jest zgodny z twoją definicją równości), najszybszym rozwiązaniem usuwania duplikatów będzie posortowanie listy (0 (n log ( n))), a następnie wykonać jedno przejście i poszukać powtórki elementów (czyli równych elementów, które następują po sobie) (to jest O (n)).

Ogólna złożoność wyniesie O (n log (n)), co jest mniej więcej tym samym, co uzyskasz za pomocą zbioru (n razy długi (n)), ale ze znacznie mniejszą stałą. Dzieje się tak, ponieważ stała sortowania / deduplikacji wynika z kosztu porównywania elementów, podczas gdy koszt z zestawu najprawdopodobniej będzie wynikał z obliczenia skrótu plus jedno (prawdopodobnie kilka) porównań hash. Jeśli używasz implementacji Set opartej na skrótach, to znaczy, ponieważ drzewo oparte na drzewie da ci O (n log² (n)), co jest jeszcze gorsze.

Jednak, jak rozumiem, nie musisz usuwać duplikatów, a jedynie testować ich istnienie. Więc powinieneś ręcznie zakodować algorytm scalania lub sortowania sterty w swojej tablicy, który po prostu kończy zwracając prawdę (tj. "Jest dup"), jeśli twój komparator zwraca 0, w przeciwnym razie kończy sortowanie i przeszukuje posortowaną tablicę testując powtórzenia . Rzeczywiście, w przypadku sortowania przez scalanie lub sortowanie po zakończeniu sortowania porównasz każdą zduplikowaną parę, chyba że oba elementy były już na swoich końcowych pozycjach (co jest mało prawdopodobne). Tak więc zmodyfikowany algorytm sortowania powinien przynieść ogromną poprawę wydajności (musiałbym to udowodnić, ale myślę, że zmodyfikowany algorytm powinien znajdować się w O (log (n)) na jednolicie losowych danych)


W tym przypadku n wynosi 6, więc nie marnowałbym dużo czasu na szczegóły implementacji, ale zatrzymam twój pomysł na specjalny rodzaj stosu, jeśli kiedykolwiek będę musiał zrobić coś takiego.
Paul Tomblin,

Nie rozumiem trzeciego akapitu. Mergesort i heapsort to O (nlog (n)), a nie O (log (n)) podczas pisania; nawet jeśli wyjdziesz po zidentyfikowaniu duplikatu, to nadal nie zmieni Twojej złożoności czasowej ...
ChaimKut

8

Musiałem wykonać podobną operację dla a Stream, ale nie mogłem znaleźć dobrego przykładu. Oto, co wymyśliłem.

public static <T> boolean areUnique(final Stream<T> stream) {
    final Set<T> seen = new HashSet<>();
    return stream.allMatch(seen::add);
}

Ma to tę zaletę, że powoduje zwarcie, gdy duplikaty są wykrywane wcześnie, zamiast przetwarzania całego strumienia i nie jest dużo bardziej skomplikowane niż umieszczenie wszystkiego w a Seti sprawdzenie rozmiaru. Więc ten przypadek byłby mniej więcej taki:

List<T> list = ...
boolean allDistinct = areUnique(list.stream());

7

W Javie 8+ możesz używać Stream API:

boolean areAllDistinct(List<Block> blocksList) {
    return blocksList.stream().map(Block::getNum).distinct().count() == blockList.size();
}

2

Mówiąc najprościej: 1) upewnij się, że wszystkie elementy są porównywalne 2) posortuj tablicę 2) powtórz po tablicy i znajdź duplikaty


1

Aby poznać duplikaty na liście, użyj następującego kodu: Otrzymasz zestaw zawierający duplikaty.

 public Set<?> findDuplicatesInList(List<?> beanList) {
    System.out.println("findDuplicatesInList::"+beanList);
    Set<Object> duplicateRowSet=null;
    duplicateRowSet=new LinkedHashSet<Object>();
            for(int i=0;i<beanList.size();i++){
                Object superString=beanList.get(i);
                System.out.println("findDuplicatesInList::superString::"+superString);
                for(int j=0;j<beanList.size();j++){
                    if(i!=j){
                         Object subString=beanList.get(j);
                         System.out.println("findDuplicatesInList::subString::"+subString);
                         if(superString.equals(subString)){
                             duplicateRowSet.add(beanList.get(j));
                         }
                    }
                }
            }
            System.out.println("findDuplicatesInList::duplicationSet::"+duplicateRowSet);
        return duplicateRowSet;
  }

1

najlepszym sposobem rozwiązania tego problemu jest użycie zestawu HashSet :

ArrayList<String> listGroupCode = new ArrayList<>();
listGroupCode.add("A");
listGroupCode.add("A");
listGroupCode.add("B");
listGroupCode.add("C");
HashSet<String> set = new HashSet<>(listGroupCode);
ArrayList<String> result = new ArrayList<>(set);

Po prostu wydrukuj arraylistę wyników i zobacz wynik bez duplikatów :)


1

Jeśli chcesz zestaw zduplikowanych wartości:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class FindDuplicateInArrayList {

    public static void main(String[] args) {

        Set<String> uniqueSet = new HashSet<String>();
        List<String> dupesList = new ArrayList<String>();
        for (String a : args) {
            if (uniqueSet.contains(a))
                dupesList.add(a);
            else
                uniqueSet.add(a);
        }
        System.out.println(uniqueSet.size() + " distinct words: " + uniqueSet);
        System.out.println(dupesList.size() + " dupesList words: " + dupesList);
    }
}

I prawdopodobnie pomyśl także o przycinaniu wartości lub używaniu małych liter ... w zależności od przypadku.


Najprostsza i najlepsza odpowiedź, jeśli chcesz duplikatów, dla wydajności możesz zainicjować wskazówkę uniqueSet z rozmiarem argumentów.
Christophe Roussy

0
    String tempVal = null;
    for (int i = 0; i < l.size(); i++) {
        tempVal = l.get(i); //take the ith object out of list
        while (l.contains(tempVal)) {
            l.remove(tempVal); //remove all matching entries
        }
        l.add(tempVal); //at last add one entry
    }

Uwaga: będzie to miało duży wpływ na wydajność, ponieważ elementy są usuwane z początku listy. Aby rozwiązać ten problem, mamy dwie możliwości. 1) wykonaj iterację w odwrotnej kolejności i usuń elementy. 2) Użyj LinkedList zamiast ArrayList. Ze względu na stronnicze pytania zadawane w wywiadach w celu usunięcia duplikatów z listy bez korzystania z innej kolekcji, powyższy przykład jest odpowiedzią. Jednak w prawdziwym świecie, jeśli będę musiał to osiągnąć, wstawię elementy z listy do zestawu, proste!


0
/**
     * Method to detect presence of duplicates in a generic list. 
     * Depends on the equals method of the concrete type. make sure to override it as required.
     */
    public static <T> boolean hasDuplicates(List<T> list){
        int count = list.size();
        T t1,t2;

        for(int i=0;i<count;i++){
            t1 = list.get(i);
            for(int j=i+1;j<count;j++){
                t2 = list.get(j);
                if(t2.equals(t1)){
                    return true;
                }
            }
        }
        return false;
    }

Przykład konkretnej klasy, która nadpisała equals():

public class Reminder{
    private long id;
    private int hour;
    private int minute;

    public Reminder(long id, int hour, int minute){
        this.id = id;
        this.hour = hour;
        this.minute = minute;
    }

    @Override
    public boolean equals(Object other){
        if(other == null) return false;
        if(this.getClass() != other.getClass()) return false;
        Reminder otherReminder = (Reminder) other;
        if(this.hour != otherReminder.hour) return false;
        if(this.minute != otherReminder.minute) return false;

        return true;
    }
}

0
    ArrayList<String> withDuplicates = new ArrayList<>();
    withDuplicates.add("1");
    withDuplicates.add("2");
    withDuplicates.add("1");
    withDuplicates.add("3");
    HashSet<String> set = new HashSet<>(withDuplicates);
    ArrayList<String> withoutDupicates = new ArrayList<>(set);

    ArrayList<String> duplicates = new ArrayList<String>();

    Iterator<String> dupIter = withDuplicates.iterator();
    while(dupIter.hasNext())
    {
    String dupWord = dupIter.next();
    if(withDuplicates.contains(dupWord))
    {
        duplicates.add(dupWord);
    }else{
        withoutDupicates.add(dupWord);
    }
    }
  System.out.println(duplicates);
  System.out.println(withoutDupicates);

Dodaj wyjaśnienie wraz z odpowiedzią, w jaki sposób ta odpowiedź pomaga OP w naprawianiu bieżącego problemu
ρяσѕρєя K

0

Ta odpowiedź jest napisana w Kotlinie, ale można ją łatwo przetłumaczyć na Javę.

Jeśli rozmiar twojego arraylisty mieści się w stałym, małym zakresie, jest to świetne rozwiązanie.

var duplicateDetected = false
    if(arrList.size > 1){
        for(i in 0 until arrList.size){
            for(j in 0 until arrList.size){
                if(i != j && arrList.get(i) == arrList.get(j)){
                    duplicateDetected = true
                }
            }
        }
    }

0
private boolean isDuplicate() {
    for (int i = 0; i < arrayList.size(); i++) {
        for (int j = i + 1; j < arrayList.size(); j++) {
            if (arrayList.get(i).getName().trim().equalsIgnoreCase(arrayList.get(j).getName().trim())) {
                return true;
            }
        }
    }

    return false;
}
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.