Given an unsorted array of integers. Write a code to remove duplicates from unsorted array.
For example:
Input :{5, 1, 2, 6, 4, 4, 5}
Output :{5, 1, 2, 6, 4}
In this example, 4 and 5 appear multiple times in an input array.
In the output, All the duplicates are removed and we have printed only distinct elements of an array.
Remove Duplicates from an Unsorted Array
In this tutorial, I am going to discuss how we can remove duplicate elements from unsorted array using multiple approaches. Also, we will discuss the time complexities and java code for each approach.
I have added a video tutorial at the end of this post.
Remove duplicates from a sorted linked list
Remove duplicates from sorted array in-place
Remove Duplicates from Unsorted Array Java Code
How to remove duplicate elements from an array? The simplest way to remove duplicates is by sorting an array.
We first sort an array. Once the array is sorted, We can easily remove duplicates by comparing current element with the next element of an array.
The time complexity of this approach is O(nlogn) and it’s space complexity is O(1).
Sorting Algorithms and their Time Complexities
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
/* Remove duplicates by sorting an array */ public class RemoveDuplicate { public static void removeDuplicateUsingSorting(int arr[]) { //Sort an unsorted array Arrays.sort(arr); int len = arr.length; int j = 0; //Traverse an array for (int i = 0; i < len - 1; i++) { //if value present at i and i+1 index is not equal if (arr[i] != arr[i + 1]) { arr[j++] = arr[i]; } } arr[j++] = arr[len - 1]; for (int k = 0; k < j; k++) { System.out.print(arr[k] + " "); } } public static void main(String[] args) { int arr[] = { 5, 1, 2, 6, 4, 4, 5, 6, 8, 7 }; removeDuplicateUsingSorting(arr); } } |
Remove Duplicates from an Unsorted Array by using HashMap
The idea here is to first count each number and it’s occurrences in an array. Once we know the number and it’s count we can easily remove duplicates from an array.
Here, I am using HashMap to store number and it’s count. So, the array element is the key and it’s count is the value. Traverse an array and put each element and it’s count. Once the map is created, print all the keys which is unique elements present in an array.
The time complexity of this approach is O(n) and it’s space complexity is also O(n).
Find first non-repeating character in a string
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
/* Remove duplicates from an unsorted array using a hashmap */ public class RemoveDuplicate { public static void removeDuplicateUsingHashing(int arr[]) { //Declare a hashmap Map<Integer, Integer> map = new HashMap<>(); int len = arr.length; //Traverse an array for (int i = 0; i < len - 1; i++) { //If key is already present in a map if (map.containsKey(arr[i])) { //Increment it's count map.put(arr[i], map.get(arr[i]) + 1); } else { /* If it's not present in a map then put a key and it's initial count 1 */ map.put(arr[i], 1); } } //Print Each Key map.forEach((k, v) -> System.out.print(k + " ")); } public static void main(String[] args) { int arr[] = { 5, 1, 2, 6, 4, 4, 5, 6, 8, 7 }; removeDuplicateUsingHashing(arr); } } |
Remove Duplicates from an Unsorted Array by using Set
Set does not allow duplicates. By using the property of a set data structure, we can remove duplicates from an array.
Traverse an array and put the array elements in a set. Once the traversal is complete, print all the elements present in a set.
The time complexity of this approach is O(n) and it’s space complexity is also O(n).
Find the element that appears once in a sorted array
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
/* Remove duplicates using set */ public class RemoveDuplicate { public static void removeDuplicateUsingSet(int arr[]) { //Declare set Set st = new HashSet<>(); int len = arr.length; //Traverse an array and add element in a set for (int i = 0; i < len - 1; i++) { //It only add unique value st.add(arr[i]); } //Print each element st.forEach(elem -> System.out.print(elem + " ")); } public static void main(String[] args) { int arr[] = { 5, 1, 2, 6, 4, 4, 5, 6, 8, 7 }; removeDuplicateUsingSet(arr); } } |
