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

Question

Suppose you are given an already sorted array that may contain duplicate items
– i.e., items that appear more than once. Add a method to the Sort class called
removeDups() that takes a sorted array of integers and removes whatever
elements are necessary to ensure that no item appears more than once. Make
your method as efficient as possible.
The remaining elements should still be sorted, and they should occupy the
leftmost positions of the array. The array locations that are unused after the
duplicates are removed should be filled with zeroes. For example, if arr is the
array {2, 5, 5, 5, 10, 12, 12}, after the call removeDups(arr), the array
should be {2, 5, 10, 12, 0, 0, 0}.
The method should return an int that specifies the number of unique values in
the array. For example, when called on the original array 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.

Explanation / Answer

public class Sort { public static void main(String []args) { int arr[]= {2, 5, 5, 5, 10, 12, 12}; int size = removeDups(arr); for( int i:arr ) System.out.print(i+" "); System.out.println(" size: "+size); } public static int removeDups(int arr[]) { int first = -1; //keeps the index of first occurence of repeated value //loop through the array elements for( int i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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