Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Removing Duplicates You are given an array of n elements, and you notice that some of the elements are duplicates; that is , they appear
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 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
sortedarray mergesortinputarray
for i n:
if sortedarrayi sortedarrayi:
removesortedarrayi
return sortedarray
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... For each item in the array... We use a hashset and store each element.. We sort our array with merge sort and then linearly scan.. sortedarray mergesortinputarrayWe run a modified merge sort... Answer key: On On log n The linear scan takes On so the overall runtime is On beating the target On log n It takes On log n to sort an array with merge sort, and then a linear scan to remove duplicates takes On total, so the final runtime is dominated by the On log n merge sort runtime., mergesort On log n; for i n On; On log n On On log n On Hashsets in this class is considered On worst case for all operations. So adding n elements to a hashset takes On time., The target runtime is On 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 with another O step so the overall runtime is unchanged giving us On log n
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started