Java: Phát hiện các bản sao trong ArrayList?

Question

Làm cách nào để phát hiện (trả về true/false) cho dù ArrayList có chứa nhiều hơn một phần tử giống nhau trong Java không?

Rất cám ơn, Terry

Sửa Quên đề cập đến rằng tôi không muốn so sánh "Blocks" với nhau nhưng giá trị số nguyên của họ. Mỗi "khối" có một int và đây là những gì làm cho chúng khác nhau. Tôi tìm thấy phần int của một Khối cụ thể bằng cách gọi một phương thức có tên là "getNum" (ví dụ: table1 [0] [2] .getNum();

Answer 1

Đơn giản nhất: đổ toàn bộ tập hợp vào một Tập hợp (sử dụng Set (Bộ sưu tập)) constructor hoặc Set.addAll), sau đó xem nếu Set có kích thước tương tự như ArrayList

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

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

cập nhật:. Nếu tôi hiểu câu hỏi của bạn một cách chính xác, bạn có một mảng 2ngày của Block, như trong

Bảng khối [] [];

và bạn muốn phát hiện xem có bất kỳ hàng của chúng có trùng lặp?

Trong trường hợp đó, tôi có thể làm những điều sau đây, giả định rằng khối thực hiện "bằng" và "hashCode" một cách chính xác:

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

Tôi không chắc chắn 100% đó cho cú pháp, vì vậy nó có thể là an toàn hơn để viết nó như

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

...

Answer 2

Nếu bạn đang tìm kiếm để tránh việc trùng ở tất cả, sau đó bạn chỉ cần cắt ra quá trình giữa phát hiện bản sao và sử dụng một Set.

Answer 3

Nếu các yếu tố của bạn bằng cách nào đó So sánh (thực tế là thứ tự có ý nghĩa thực sự là vô tư - nó chỉ cần nhất quán với định nghĩa bình đẳng của bạn), giải pháp loại bỏ trùng lặp nhanh nhất sắp xếp danh sách (0 (n log (n))) sau đó thực hiện một lần truyền và tìm kiếm các thành phần lặp lại (có nghĩa là, các phần tử bằng nhau theo sau) (đây là O (n)).

Độ phức tạp tổng thể sẽ là O (n log (n)), gần giống như những gì bạn nhận được với một Set (n lần dài (n)), nhưng với một hằng số nhỏ hơn nhiều. Điều này là do hằng số trong sắp xếp/dedup kết quả từ chi phí so sánh các phần tử, trong khi chi phí từ tập hợp có nhiều khả năng là kết quả từ một phép tính băm, cộng với một (có thể một số) so sánh băm. Nếu bạn đang sử dụng cài đặt Tập hợp dựa trên băm, nghĩa là, vì một Cây dựa trên sẽ cung cấp cho bạn một O (n log² (n)), điều này thậm chí còn tồi tệ hơn.

Tuy nhiên, tôi hiểu rằng bạn không cần phải xóa trùng lặp mà chỉ kiểm tra sự tồn tại của chúng. Vì vậy, bạn nên viết mã một thuật toán sắp xếp hợp nhất hoặc đống trên mảng của bạn, mà chỉ đơn giản là thoát trở lại đúng (nghĩa là "có một") nếu so sánh của bạn trả về 0, và nếu không hoàn thành sắp xếp, và đi qua kiểm tra mảng được sắp xếp để lặp lại . Trong một sắp xếp hợp nhất hoặc đống, thực sự, khi sắp xếp được hoàn thành, bạn sẽ so sánh mọi cặp trùng lặp trừ khi cả hai phần tử đã ở vị trí cuối cùng của chúng (điều này không chắc chắn).Do đó, thuật toán sắp xếp tinh chỉnh sẽ mang lại hiệu suất rất lớn (tôi sẽ phải chứng minh điều đó, nhưng tôi đoán thuật toán được chỉnh sửa phải ở trong O (log (n)) trên dữ liệu ngẫu nhiên thống nhất)

Answer 4

Đơn giản chỉ cần đặt: 1) chắc chắn rằng tất cả các mục có thể so sánh 2) sắp xếp các mảng 2) lặp qua mảng và tìm thấy bản sao

Answer 5

Cải thiện mã, sử dụng giá trị trả về của Set#add thay vì so sánh kích thước của danh sách và thiết lập.

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

Answer 6

Cải thiện mã để quay trở lại các yếu tố trùng lặp

• có thể tìm thấy bản sao trong một Bộ sưu tập
• trở lại các thiết lập trùng lặp
• Unique Elements có thể được lấy từ các Set

---

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

Answer 7

Để biết các Bản sao trong Danh sách, hãy sử dụng mã sau: Nó sẽ cung cấp cho bạn tập hợp chứa các bản sao.

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

Answer 8

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 
    } 

Lưu ý: điều này sẽ có hiệu suất lớn hit mặc dù là mặt hàng được loại bỏ từ lúc bắt đầu của danh sách. Để giải quyết vấn đề này, chúng tôi có hai tùy chọn. 1) lặp lại theo thứ tự ngược và loại bỏ các phần tử. 2) Sử dụng LinkedList thay vì ArrayList. Do các câu hỏi thiên vị được yêu cầu trong các cuộc phỏng vấn để xóa các mục trùng lặp khỏi Danh sách mà không sử dụng bất kỳ bộ sưu tập nào khác, ví dụ trên là câu trả lời. Trong thế giới thực, mặc dù, nếu tôi phải đạt được điều này, tôi sẽ đặt các yếu tố từ List to Set, đơn giản!

Answer 9

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

Một ví dụ về một lớp bê tông đã ghi đè 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; 
    } 
} 

Answer 10

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

Answer 11

tôi cần phải làm một thao tác tương tự cho một Stream, nhưng không thể tìm thấy một ví dụ tốt. Đây là những gì tôi nghĩ ra.

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

này có lợi thế là chập mạch khi bản sao được phát hiện sớm thay vì phải xử lý toàn bộ dòng và không có nhiều phức tạp hơn chỉ cần đặt tất cả mọi thứ trong một Set và kiểm tra kích thước. Vì vậy, trường hợp này sẽ xấp xỉ là:

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

Answer 12

Cách tốt nhất để giải quyết vấn đề này là sử dụng một 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); 

Just in kết quả ArrayList và xem kết quả mà không cần bản sao :)

Answer 13

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