Menu
I have an unsorted array, what is the best method to remove all the duplicates of an element if present?
e.g:
a[1,5,2,6,8,9,1,1,10,3,2,4,1,3,11,3] so after that operation the array should look like
a[1,5,2,6,8,9,10,3,4,11] 
218
We can remove duplicate element in an array by 2 ways: using temporary array or using separate index. To remove the duplicate element from array, the array must be in sorted order. If array is not sorted, you can sort it by calling Arrays. sort(arr) method.
To remove the duplicates from the arraylist, we can use the java 8 stream api as well. Use steam's distinct() method which returns a stream consisting of the distinct elements comparing by object's equals() method. Collect all district elements as List using Collectors. toList() .
The naive solution is to check every element against every other element. This is wasteful and yields an O(n2) solution, even if you only go "forward".
A better solution is sort the array and then check each element to the one next to it to find duplicates. Choose an efficient sort and this is O(n log n).
The disadvantage with the sort-based solution is order is not maintained. An extra step can take care of this however. Put all entries (in the unique sorted array) into a hashtable, which has O(1) access. Then iterate over the original array. For each element, check if it is in the hash table. If it is, add it to the result and delete it from the hash table. You will end up with a resultant array that has the order of the original with each element being in the same position as its first occurrence.
If you're dealing with integers of some fixed range you can do even better by using a radix sort. If you assume the numbers are all in the range of 0 to 1,000,000 for example, you can allocate a bit vector of some 1,000,001. For each element in the original array, you set the corresponding bit based on its value (eg a value of 13 results in setting the 14th bit). Then traverse the original array, check if it is in the bit vector. If it is, add it to the result array and clear that bit from the bit vector. This is O(n) and trades space for time.
Which leads us to the best solution of all: the sort is actually a distraction, though useful. Create a hashtable with O(1) access. Traverse the original list. If it is not in the hashtable already, add it to the result array and add it to the hash table. If it is in the hash table, ignore it.
This is by far the best solution. So why the rest? Because problems like this are about adapting knowledge you have (or should have) to problems and refining them based on the assumptions you make into a solution. Evolving a solution and understanding the thinking behind it is far more useful than regurgitating a solution.
Also, hash tables are not always available. Take an embedded system or something where space is VERY limited. You can implement an quick sort in a handful of opcodes, far fewer than any hash table could be.
62
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
