Java: wykryć duplikaty w ArrayList?

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

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.

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

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

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

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)

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

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

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

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

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

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 :)

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.

    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!

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

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

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

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