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... Let's find the matching runtime analysis.

Note that while some final runtimes are the same, we are looking for the one that matches each solution... $1.$ For each item in the array... $2.$We use a hashset and store each element..$\mathrm{.}3.$ We sort our array with merge sort and then linearly scan..$\mathrm{.}4.$ sorted$\_$array $=$ merge$\_$sort$($input$\_$array$)..\mathrm{.}5.$We run a modified merge sort... Answer key: O$($n$^2),$ O$($n log n$),$ The linear scan takes O$($n$)$ so the overall runtime is O$($n$)$ beating the target O$($n log n$).,$ It takes O$($n log n$)$ to sort an array with merge sort, and then a linear scan to remove duplicates takes O$($n$)$ total, so the final runtime is dominated by the O$($n log n$)$ merge sort runtime., merge$\_$sort$()=$ O$($n log n$)$; for i $=1->$n$-1=$ O$($n$)$; O$($n log n$)+$ O$($n$)=$ O$($n log n$),$ O$($n$),$ Hashsets in this class is considered O$($n$)$ worst case for all operations. So adding n elements to a hashset takes O$($n$^2)$ time., The target runtime is O$($n log n$)$ so my correct solution would have that runtime obviously., We don't need runtimes for D&C solutions., We add to the mergesort comparison step which is O$(1)$ with another O$(1)$ step so the overall runtime is unchanged giving us O$($n log n$)$