Removing Duplicates

You are given an array of n elements, and you notice that some of the elements are duplicates; that is$,$ they appear more than once in the array. Provide an algorithm to remove all duplicates from the array. $($Note that any sorting is accomplished using the merge sort algorithm.$)$

Consider the following algorithms and pick any that would receive full credit in this class. There may be more than one such answer.

For simplicity we will consider removal from the array to be O$(1)$ since we can just as easily write the solution to a new array:

a$.$

For each item in the array, we compare it to all other items in the array and if we see more than one, remove the additional occurrences and return the final array as our solution.

b$.$

We use a hashset and store each element in the set as we see it$.$ If it already exists in the set then it won't be added again so any duplicates will automatically be ignored. Once we are done, return the elements in the set as an array.

c$.$

We sort our array with merge sort and then linearly scan the sorted array to remove any elements that are identical to the previous element. Returning the final array with duplicates removed.

d$.$

sorted$\_$array $=$ merge$\_$sort$($input$\_$array$)$

for i $=1->$n$-1$:

if sorted$\_$array$[$i$]==$ sorted$\_$array$[$i$+1]$:

remove$($sorted$\_$array$[$i$])$

return sorted$\_$array

e$.$

We run a modified merge sort such that each merge step will check if left and right are the same, if they are then discard the right element and continue the merge step as normal. Return the sorted array with duplicates removed.