Removing duplicates from array
Given an unsorted array of integers, remove all duplicates from it. For example if input array is A = [2,3,4,4,1,2,3,3]
Final output should be A = [2,3,4,1] where duplicates of 2,4 and 1 are removed. Notice that it is not necessary that duplicates are clubbed together in array.
First option which comes to mind is to sort given array using quick sort or merge sort with O(nlogn) complexity and then in linear time remove all duplicates as all duplicates will then be together.
Detailed explanation how duplicates from a sorted array can be removed is given in this post :
How about if the constraint is not to sort array first, other way to put this constraint is to say that elements in output array should preserve the order they were in input array.
Some basic algorithm to remove duplicate elements will be to start from first element till the last element repeat following
Check from the next element to last element, if element matches the current element of step 1,
move all the elements on right side of this element by one left. Let’s code it
Complexity of this algorithm to remove duplicates from array will be O(N^3)
Other method of solving this problem is to use binary search tree. Construct a binary search tree using elements of array and discard all elements which are duplicates. Tree will contain only non duplicate values,however, order in original array is not maintained in this solution.
Complexity of above code is O(nlogn) for each node insertion will take O(logn) and there are n nodes to be added.
Last but most efficient solution is to use merge sort and remove duplicates in merge step. This solution requires extra book keeping while merge step of merge sort. I have written the merge sort, book keeping I still need to figure that out, if you have some hints, please comment or drop me a mail.