What is the most efficient way to identify and remove the duplicate in an array?

Question

I have an array with 1 million objects and it contains 1 duplicate? What is the most efficient way to identify the duplicate and remove it?

Possible duplicate of [Finding out the duplicate element in an array](http://stackoverflow.com/questions/7117388/finding-out-the-duplicate-element-in-an-array) — OneCricketeer, Nov 10 '15 at 13:33

score 0 · Answer 1 · answered Nov 10 '15 at 13:29

If it is sorted, just go from left to right until you find two of them in row

Average complexity : O(n/2)

Worst complexity : O(n)
If it is not sorted and you have enough memory, create hashmap, store objects as keys and when you hit one key twice, it is duplicate.

Average complexity : O(n/2)

Worst complexity : O(n)
If it is not sorted and you do not have enough memory, use quicksort to sort it and then use approach no. 1

Average complexity : O(n*log n)

Worst complexity : O(n^2)

1 Answers1