hi all, im having trouble to determine the best way to solve this problem
suppose that you have an array of integers and you want to remove duplicates
i have thought of some solutions but im not sure
1) i create a second array and for every element in the original array i check if it's in the second array using a second loop, if it's not there, i add it to the second array, else i go to the next element of the first array..
i think we have worst case when there are no duplicates, and the complexity is O(n^2)
2) use heapsort O(n*logn) to sort the array and then I use a pointer to the element im about to check, I then use a counter to loop the array and I remove the values that are equals to the value the pointers is pointing to, but the problem is that I remove them by bringing back all the elements of the remaining array, doesn't this give us O(n*logn) + O(n^2) = O(n^2) or is it O(n*logn) + O(n) = O(n*logn)?
3) use an avl tree, or a simple binary tree, add the values of the original array there, then use inorder/preorder/postorder and add each element to the final array, this gives us O(n*logn) for adding and O(n) for inorder so it's O(n*logn) right?
4) use a hash table.. add the elements in the hash table -> O(1) for each element hence O(n), then loop for each element and see if it's there or not, if it's there i dont put it in the final array, else i put it in the final array
so assuming that checking if an element is in the hash table gives O(1) for each element, this gives us O(n) + O(n) = O(n) complexity..
im not sure if these complexities i've calculated are correct.. can you please help me?
which is the best method? thanks in advance