Java: duplicate detection in ArrayList?

Question

How can I find a definition (returning true / false), does the ArrayList contain more than one element from Java?

Thanks a lot Terry

Edit I forgot to mention that I am not going to compare the "blocks" with each other, but their integer values. Each "block" has an int, and this is what makes them different. I find the int of a specific block by calling a method named getNum (for example, table1 [0] [2] .getNum ();

Answer 1

The easiest way is to upload the entire collection to Set (using the Set (Collection) constructor or Set.addAll constructor), and then see if the Set is the same size as the ArrayList.

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

Update: if I understand your question correctly, you have a 2d block array, as in

Lock table [] [];

and you want to determine if there are duplicates in each row?

In this case, I could do the following, assuming Block implements equals and hashCode correctly:

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

I am not 100% sure of the syntax, so it would be safer to write it as

 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.add returns a boolean false if the item being added is already in the set, so you can even short-circuit and unload any add that returns false if all you want to know is the presence of duplicates. ,

Answer 2

Improved code by using the return value of Set#add instead of comparing the size of the list and the set.

 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 3

If you want to avoid duplication at all, you should just cut out the average duplicate detection process and use Set .

Answer 4

Improved code to return duplicate items

• You can find duplicates in the collection
• return a set of duplicates
• Unique items can be obtained from 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 5

If your elements are somehow comparable (the fact that the order has some real meaning is indifferent - it just needs to match your definition of equality), the fastest solution for removing duplicates is going to sort the list (0 (n log (n))) , then do one pass and look for duplicate elements (that is, equal elements that follow each other) (this is O (n)).

The overall complexity will be O (n log (n)), which roughly coincides with what you get with Set (n times long (n)), but with a much lower constant. This is due to the fact that the constant in sort / dedup arises because of the cost of comparing the elements, while the cost from the set is likely to be the result of computing the hash, plus one (possibly several) hash comparisons. If you use a hash-based Set implementation, that is because Tree based will give you O (n log² (n)), which is even worse.

However, as I understand it, you do not need to delete duplicates, but simply check their existence. Thus, you must manually compile the merge or heap sorting algorithm in your array, which simply returns a return value of true (ie, "There is a duplicate") if your comparator returns 0 and otherwise completes the sorting and passes the sorted array check for repetitions, In the case of a merge or a heap, indeed, when the sorting is completed, you will compare each repeated pair if both elements are no longer in their final positions (which is unlikely). Thus, the selective sorting algorithm should give a huge increase in performance (I would have to prove it, but, I think, the algorithm with the modified algorithm should be in O (log (n)) on uniformly random data)

Answer 6

I needed to perform a similar operation for Stream , but could not find a good example. Here is what I came up with.

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

This has the advantage of short circuiting when duplicates occur earlier, rather than processing the entire stream and not much more complicated than just putting everything in Set and checking the size. So this case would be something like this:

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

Answer 7

With Java 8+, you can use the Stream API:

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

Answer 8

Simply put: 1) make sure that all elements are comparable 2) sort the array 2) iterate over the array and search for duplicates

Answer 9

To find duplicates in a list, use the following code: it will give you a set containing duplicates.

  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 10

If you want to set duplicate values:

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

And maybe also think about cropping values ​​or using lowercase letters ... depending on your case.

Answer 11

The best way to deal with this problem is to use a 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 print the result of arraylist and see the result without duplicates :)

Answer 12

  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 } 

Note. This will have great performance though, as items are removed from the top of the list. To solve this problem, we have two options. 1) iterate in reverse order and remove elements. 2) Use LinkedList instead of ArrayList. Due to biased questions asked in the interview to remove duplicates from the list without using any other collection, the above example is the answer. In the real world, though, if I have to achieve this, I will put the items from the list in Set, simply!

Answer 13

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

An example of a specific class that overrides 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 14

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

Answer 15

This answer is written in Kotlin, but can be easily translated into Java.

If your array size is within a fixed small range, then this is a great solution.

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