Suppose you are given an already sorted list that may contain duplicate items –

Question

Suppose you are given an already sorted list that may contain duplicate items – i.e., items that appear more than once. Add a method to the SortCount class (in SortCount.py) called removeDups() that takes a sorted list of integers and removes whatever elements are necessary to ensure that no item appears more than once. Make your method as efficient as possible in the number of operations that it performs. In addition, your method should use O(1) additional memory – i.e., it should not create and use a second list.

The remaining elements should still be sorted, and they should occupy the leftmost positions of the list. The list locations that are unused after the duplicates are removed should be filled with zeroes. For example, if alist is the list [2, 5, 5, 5, 10, 12, 12], after the call removeDups(alist), the list should be [2, 5, 10, 12, 0, 0, 0].

The method should return an integer that specifies the number of unique values in the list. For example, when called on the original list above, the method should return a value of 4. Add code to the main method to test your new method.

Important note: One inefficient approach would be to scan from left to right, and, whenever you encounter a duplicate, to shift all of the remaining elements left by one. The problem with this approach is that elements can end up being shifted multiple times, and thus the algorithm has a worst-case running time that is O(n2). Your method should move each element at most once. This will give it a running time that is O(n). Only half credit will be given for methods that move elements more than once.Use Python!!

HERE IS THE STARTING CODE I AM GIVEN.

Explanation / Answer

for i, item in enumerate(lst):
if lst[i] >a:
b=b+1
lst[b]=lst[i]
a=lst[b]
for i in xrange(len(lst)-1, b, -1):
lst[i]=0
return b
  

Note:Elements are moved only once and no another list is used as per the requirement.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.