3 Ways To Discovery Duplicate Elements Inward An Array - Java

There are multiple ways to respect duplicate elements inward an array inward Java together with nosotros volition meet iii of them inward this program. Solution together with logic shown inward this article are generic together with applies to an array of whatever type e.g. String array or integer array or array of whatever object. One of the most mutual way to respect duplicates is past times using animate beingness forcefulness method, which compares each chemical constituent of the array to every other element. This solution has the fourth dimension complexity of O(n^2) and alone exists for the academic purpose. You shouldn't endure using this solution inward the existent world. The measure way to respect duplicate elements from an array is past times using HashSet information structure. If yous remember, Set abstract information type doesn't allow duplicates. You tin give the axe direct maintain payoff of this belongings to filter duplicate elements. This solution has a fourth dimension complexity of O(n), equally yous alone demand to iterate over array once, merely likewise has infinite complexity of O(n) as yous demand to shop unique elements inward the array.


Our third solution to respect duplicate elements inward an array is genuinely similar to our minute solution merely instead of using Set information construction nosotros volition usage hash tabular array information structure. This is a pretty expert solution because yous tin give the axe extend it to flora count of duplicates equally well. In this solution, nosotros iterate over the array together with construct the map which stores array elements together with their count. Once the tabular array is build, yous tin give the axe iterate over a hash tabular array together with impress out all the elements, who has a count greater than one, those are your duplicates.

How to respect duplicates inward Java array?

In the get-go paragraph, I direct maintain given yous a brief overview of iii ways to respect duplicate elements from Java array. Now, let's sympathize the logic behind each of those solutions inward footling to a greater extent than detail.

Solution 1 :

Our get-go solution is really simple. All nosotros are doing hither is to loop over an array together with comparison each chemical constituent to every other element. For doing this, nosotros are using 2 loops, inner loop, together with outer loop. We are likewise making certain that nosotros are ignoring comparison of elements to itself past times checking for i != j before printing duplicates. Since nosotros are comparison every chemical constituent to every other element, this solution has quadratic fourth dimension complexity i.e. O(n^2). This solution has the worst complexity inward all iii solutions.

 for (int i = 0; i < names.length; i++) {      for (int j = i + 1 ; j < names.length; j++) {           if (names[i].equals(names[j])) {                    // got the duplicate element           }      }  }

This interrogation is likewise really pop on programming interviews together with if yous are preparing for them, I likewise advise yous to solves problems from Cracking the Coding Interview: 150 Programming Questions together with Solutions. One of the best majority to laid upwards for software developer interviews.

Solution 2 :

Second solution is fifty-fifty simpler than this. All yous demand to know is that Set doesn't allow duplicates inward Java. Which way if yous direct maintain added an chemical constituent into Set together with trying to insert duplicate chemical constituent again, it volition non endure allowed. In Java, yous tin give the axe usage HashSet shape to solve this problem. Just loop over array elements, insert them into HashSet using add() method together with banking concern tally furnish value. If add() returns fake it way that chemical constituent is non allowed inward the Set together with that is your duplicate. Here is the code sample to create this :

 for (String name : names) {      if (set.add(name) == false) {         // your duplicate element      } }

Complexity of this solution is O(n) because yous are alone going through array 1 time, merely it likewise has infinite complexity of O(n) because of HashSet information structure, which contains your unique elements. So if an array contains 1 1 chiliad one thousand elements, inward worst representative yous would demand an HashSet to shop those 1 1 chiliad one thousand elements.

Solution 3 :

Our 3rd solution takes payoff of some other useful information structure, hash table. All yous demand to create is loop through the array using enhanced for loop together with insert each chemical constituent together with its count into hash table. You tin give the axe usage HashMap shape of JDK to solve this problem. It is the full general piece of work hash tabular array implementation inward Java. In companionship to construct table, yous banking concern tally if hash tabular array contains the elements or not, if it is so increment the count otherwise insert chemical constituent amongst count 1. Once yous direct maintain this tabular array ready, yous tin give the axe iterate over hashtable together with impress all those keys which has values greater than one. These are your duplicate elements. This is inward fact a really expert solution because yous tin give the axe extend it to flora count of duplicates equally well. If yous remember, I direct maintain used this approach to find duplicate characters inward String earlier. Here is how yous code volition await similar :

// construct hash tabular array amongst count         for (String name : names) {             Integer count = nameAndCount.get(name);             if (count == null) {                 nameAndCount.put(name, 1);             } else {                 nameAndCount.put(name, ++count);             }         }          // Print duplicate elements from array inward Java         Set<Entry<String, Integer>> entrySet = nameAndCount.entrySet();         for (Entry<String, Integer> entry : entrySet) {             if (entry.getValue() > 1) {                 System.out.printf("duplicate chemical constituent '%s' together with count '%d' :", entry.getKey(), entry.getValue());             }         } 

Time complexity of this solution is O(2n) because nosotros are iterating over array twice together with infinite complexity is same equally previous solution O(n). In worst representative yous would demand a hash tabular array amongst size of array itself.

Java Program to respect duplicate elements inward array

Here is our iii solutions packed into a Java computer programme to respect duplicate elements inward array. You tin give the axe run this representative from ascendency business or Eclipse IDE, whatever suits you. Just brand certain that mention of your Java rootage file should endure same equally your populace shape e.g. "DuplicatesInArray". I direct maintain left flake of exercise for you, of course of educational activity if yous would similar to do. Can yous refactor this code into methods, yous tin give the axe create that easily past times using extract method characteristic of IDE similar Eclipse together with Netbans together with write unit of measurement assay to banking concern tally the logic of each approach. This would give yous some practise inward refactoring code together with writing JUnit tests, 2 of import attributes of a professional person programmer.

package dto;  import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Map.Entry; import java.util.Set;  /**  * Java Program to respect duplicate elements inward an array. There are 2 right away  * forwards solution of this occupation first, animate beingness forcefulness way together with minute past times using  * HashSet information structure. Influenza A virus subtype H5N1 3rd solution, similar to minute 1 is past times using  * hash tabular array information construction e.g. HashMap to shop count of each chemical constituent together with  * impress chemical constituent amongst count 1.  *   * @author java67  */  public class DuplicatesInArray{      public static void main(String args[]) {          String[] names = { "Java", "JavaScript", "Python", "C", "Ruby", "Java" };          // First solution : finding duplicates using animate beingness forcefulness method         System.out.println("Finding duplicate elements inward array using animate beingness forcefulness method");         for (int i = 0; i < names.length; i++) {             for (int j = i + 1; j < names.length; j++) {                 if (names[i].equals(names[j]) ) {                    // got the duplicate element                 }             }         }          // Second solution : usage HashSet information construction to respect duplicates         System.out.println("Duplicate elements from array using HashSet information structure");         Set<String> shop = new HashSet<>();          for (String mention : names) {             if (store.add(name) == false) {                 System.out.println("found a duplicate chemical constituent inward array : "                         + name);             }         }          // Third solution : using Hash tabular array information construction to respect duplicates         System.out.println("Duplicate elements from array using hash table");         Map<String, Integer> nameAndCount = new HashMap<>();          // construct hash tabular array amongst count         for (String mention : names) {             Integer count = nameAndCount.get(name);             if (count == null) {                 nameAndCount.put(name, 1);             } else {                 nameAndCount.put(name, ++count);             }         }          // Print duplicate elements from array inward Java         Set<Entry<String, Integer>> entrySet = nameAndCount.entrySet();         for (Entry<String, Integer> entry : entrySet) {              if (entry.getValue() > 1) {                 System.out.println("Duplicate chemical constituent from array : "                         + entry.getKey());             }         }     } } Output : Finding duplicate elements inward array using animate beingness forcefulness method Duplicate elements from array using HashSet information construction flora a duplicate chemical constituent inward array : Java Duplicate elements from array using hash tabular array Duplicate chemical constituent from array : Java

From the output, yous tin give the axe meet that the alone duplicate chemical constituent from our String array, which is "Java" has been flora past times all of our iii solutions.


That's all about how to respect duplicate elements inward an array inward Java. In this tutorial, yous direct maintain learned iii ways to solve this problem. The animate beingness forcefulness way require yous to compare each chemical constituent from array to another, thus has quadratic fourth dimension complexity. You tin give the axe optimize functioning past times using HashSet information structure, which doesn't allow duplicates. So a duplicate chemical constituent is the 1 for which add() method of HashSet furnish false. Our 3rd solution uses hash tabular array information construction to brand a tabular array of elements together with their count. Once yous construct that table, iterate over it together with impress elements whose count is greater than one. This is a really expert coding occupation together with often asked inward Java Interview. It likewise shows how usage of a correct information construction tin give the axe amend functioning of algorithm significantly.

If yous direct maintain similar this coding problem, yous may likewise similar to solve next coding problems from Java Interviews :

• How to respect all pairs on integer array whose total is equal to given number? [solution]
• How to take duplicates from an array inward Java? [solution]
• How to kind an array inward house using QuickSort algorithm? [solution]
• Write a computer programme to respect plow over 2 numbers from an integer array? [solution]
• How create yous take duplicates from array inward place? [solution]
• How create yous contrary array inward house inward Java? [solution]
• Write a computer programme to respect missing publish inward integer array of 1 to 100? [solution]
• How to banking concern tally if array contains a publish inward Java? [solution]
• How to respect maximum together with minimum publish inward unsorted array? [solution]

Further Learning
The Coding Interview Bootcamp: Algorithms + Data Structures
Data Structures together with Algorithms: Deep Dive Using Java
Algorithms together with Data Structures - Part 1 together with 2

Recommended books to Prepare for Software Engineer Interviews

If yous are solving these coding problems to laid upwards for software engineer chore interviews, yous tin give the axe likewise direct maintain a await at next books. They incorporate wealth of cognition together with several often asked coding problems from Java together with C++ interviews :

• Programming Interviews Exposed: Secrets to Landing Your Next Job (book)
• Coding Puzzles: Thinking inward code By codingtmd (book)
• Cracking the Coding Interview: 150 Programming Questions together with Solutions (book)

Bagikan Artikel ini