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

ID: 3590450 • Letter: S

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. (You can obtain the Sort class here.)

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 array.

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 mainmethod 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(n²). 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

import java.io.*;
import java.util.Scanner;

public class RemoveDuplicate
{

public static void main(String args[]) throws IOException {

       int[] input = new int[]{2, 5, 5, 5, 10, 12, 12};
       int startIndex=0;
       int nextIndex=0;

       for (int i = 0; i < input.length; i++) {

           if(input[startIndex]==input[nextIndex])
           {
               if(startIndex!=nextIndex)
                   input[nextIndex]=0;


           }
           else
           {
               input[++startIndex]=input[nextIndex];
               if(startIndex!=nextIndex)
                   input[nextIndex]=0;

           }
           if(nextIndex<input.length)
               ++nextIndex;


       }


       for (int i = 0; i < input.length; i++)
       {
           System.out.print(" "+input[i]);
       }

}
}

OUTPUT:

2 5 10 12 0 0 0

Navigate

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

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

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

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

Question

Explanation / Answer

Related Questions

Navigate