Detecting duplicate elements in Java array is another programming interview question I like. There could be lot of way you can check if your array contains duplicate elements or not and sometime you discover a unique way of checking duplicates by asking this question on Java interview. Beauty of this question is that it has endless number of follow-up question so if interviewee get through this question you can ask to him about time complexity and space or to improve his algorithm to make it fast .you can even ask to find those duplicate elements in Array which even can go from one duplicate to many repeating elements in Array. As I said you can really test programming skill around array of a Java programmer.
Checking Array for duplicate elements Java
In this Java tutorial we will see couple of ways to find if array contains duplicates or not in Java. We will use unique property of Java collection class Set which doesn’t allow duplicates to check java array for duplicate elements. Here are five ways we can check if an array has duplicates or not:
1) brute force method which compares each element of Array to all other elements and return true if it founds duplicates. Though this is not an efficient choice it is the one which first comes in mind.
2) Another quick way of checking if a Java array contains duplicates or not is to convert that array into Set. Since Set doesn’t allow duplicates size of corresponding Set will be smaller than original Array if Array contains duplicates otherwise size of both Array and Set will be same.
3) One more way to detect duplication in java array is adding every element of array into HashSet which is a Set implementation. Since add(Object obj) method of Set returns false if Set already contains element to be added, it can be used to find out if array contains duplicates in Java or not.
In next section we will complete code example of all three ways of duplicate detection on Array in java. Remember this discussion is just confirming whether array contains duplicate or not , its not finding out actual duplicate elements from Array, though you can easily extend example Java program to accomplish that task based on your requirement.
Code Example of checking duplicate on Array in Java
Here is complete code sample of all above methods to check if your array contains duplicates or not.
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class CheckDuplicatesInJavaArray {
public static void main(String args[]) {
String[] withDuplicates = new String[] {"one","two","three","one"};
String[] withoutDuplicates = new String[] {"one","two","three"};
System.out.println("Checking array with duplicate using brute force: " + bruteforce(withDuplicates));
System.out.println("Checking array without any duplicate using brute force: " + bruteforce(withoutDuplicates));
System.out.println("Checking array with duplicate using Set and List: " + checkDuplicateUsingSet(withDuplicates));
System.out.println("Checking array without any duplicate using Set and List: " + checkDuplicateUsingSet(withoutDuplicates));
System.out.println("Checking array with duplicate using Set and List: " + checkDuplicateUsingAdd(withDuplicates));
System.out.println("Checking array without any duplicate using Set and List: " + checkDuplicateUsingAdd(withoutDuplicates));
}
/*
* brute force way of checking if array contains duplicates in Java
* comparing each elements to all other elements of array
* complexity on order of O(n^2) not advised in production
*/
public static boolean bruteforce(String[] input) {
for (int i = 0; i < input.length; i++) {
for (int j = 0; j < input.length; j++) {
if (input[i].equals(input[j]) && i != j) {
return true;
}
}
}
return false;
}
/*
* detect duplicate in array by comparing size of List and Set
* since Set doesn't contain duplicate, size must be less for an array which contains duplicates
*/
public static boolean checkDuplicateUsingSet(String[] input){
List inputList = Arrays.asList(input);
Set inputSet = new HashSet(inputList);
if(inputSet.size()< inputList.size())
return true;
}
return false;
}
/*
* Since Set doesn't allow duplicates add() return false
* if we try to add duplicates into Set and this property
* can be used to check if array contains duplicates in Java
*/
public static boolean checkDuplicateUsingAdd(String[] input) {
Set tempSet = new HashSet();
for (String str : input) {
if (!tempSet.add(str)) {
return true;
}
}
return false;
}
}
Output:
Checking array with duplicate using brute force: true
Checking array without any duplicate using brute force: false
Checking array with duplicate using Set and List: true
Checking array without any duplicate using Set and List: false
Checking array with duplicate using Set and List: true
Checking array without any duplicate using Set and List: false
That’s all on how to check if an Array contains duplicate or not in Java. You see we have used Java Collection API in two of our example, there can be other pure programming solution as well. You may be asked to detect duplicates without using Java API in real interview. Let us know if you come across some other good way of checking duplicates in array without using Java API.
Other Java Tutorials you may find useful
Tidak ada komentar:
Posting Komentar