Question

in java code

In the class Hw2, write a method removeDuplicates that given a sorted array, (1) removes the duplicates so that each distinct element appears exactly once in the sorted order at beginning of the original array, and (2) returns the number of distinct elements in the array. The following is the header of the method:

public static int removeDuplicates(int[ ] A)

For example, on input A=0, 0, 1, 1, 1, 2, 2, 3, 3, 4, your method should:

• Return 5 as the number of distinct elements.

• Have distinct elements 0, 1, 2, 3, 4 occupy the first 5 slots of the original array A. That is, after the method, the array A should look like A=0, 1, 2, 3, 4, *, *, *, *, *, where each * is a “don’t care”, that is, we don’t care what element occupies that slot.

Your method must have time complexity On and space complexity O1, where n is the length of the input array.

Hint: Use two pointers.

Answer 1

public class Main
{
public static int removeDuplicates(int[ ] A)
{
int len=A.length,k=0;
for(int i=0;i<len;)
{
int j=i+1;
while(j<len&&A[j]==A[i])
{
j++;
}
if(j<len)
{
k++;
A[k]=A[j];
}
i=j;
}
return (len>0?(k+1):0);
}
   public static void main(String[] args)
   {
   int[] A = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
       System.out.println(removeDuplicates(A));
for(int i=0;i<A.length;i++)
       System.out.print(A[i]+" ");
   }
}