Monday, May 16, 2016

Remove duplicates from sorted array.

There are a number of approaches when it comes to remove the duplicates, from the array. Here are some of them:

  1. Make a Set out of the array so that you have only the unique elements out of it, also considering the further point if you want to keep track of the order of the elements you can use LinkedHashSet that guarantees the uniqueness as well as order of the Collection.
  2. Next approach is bit granular and we traverse the array and keeps on pushing the pointers till I am getting the same element:
    1. Start with 2 pointers first marked at 0 (since it is an array, lets name it as f) and second marked at 1(lets name it as s).
    2. Keep incrementing the second pointer till the elements at ARRAY[f] and ARRAY[s] are equal.
    3. When above condition is false make ARRAY[f] = ARRAY[s] and increment both f and s since the position of f and s are traversed.
Coming to the implementation, here is the working code.

This is the code you can find the running code here.

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone
{
      public static int[] duplicatesRemoval(int[] input){
 
        int f = 0;
        int s = 1;
        //RETURN IF THE ARRAY LENGTH IS LESS THAN 2;
        if(input.length < 2){
            return input;
        }
        while(s < input.length){
            if(input[s] == input[f]){
                s++;//
            }else{
             /*
             **THIS PART CAN BE SHORTENED BY input[++f] = input[s++];
             */
             f++;//SINCE LAST POSITION IS 1 BACK TO CURRENT ONE
                input[f] = input[s];
                s++;//SINCE s POSITION IS ALREADY TRAVERSED SO INCREMENT IT
            }   
        }
        //reassigning to new array element
        int[] result = new int[f+1];
        for(int k=0; k<result.length; k++){
            result[k] = input[k];
        }
 
        return result;
    }
    public static void main(String a[]){
        int[] input = {2,3,6,6,8,9,10,10,10,12,12};
        int[] output = duplicatesRemoval(input);
        for(int i:output){
            System.out.print(i+" ");
        }
    }
}

No comments:

Post a Comment