Monday, August 24, 2015

[Two Pointers] Remove Duplicates from Sorted Array

1. Example
a= [1,1,2]
=> a = [1,2] return new array length 2


2. Implementation
Thought 1:
Q1: detect duplicate ?
A1: keep one lastElement to compare with next element
if same, no change
if different, lastElement reset to current element
Q1: care about length
A1: how many different element, increment count (use index here so bias 1)
Q1:in-palce or how to remove duplicate element in an array ?
A1: record first duplicate happening position (index) and replace with next non-duplicate value

Thought2: check duplicate length and total length - duplicate length
Q1: duplicate length?
A1: compare with prev if equal, then duplicate length +1
// NOTE: no duplicate can happen
// NOTE: last+1 since last is index and so length should be plus 1
// NOTE :snippet
if ( nums[cur] == nums[last] ) {
  cur++; 
}
 else {
 last++;
 nums[last] = nums[cur]; 
cur++; 
}
// Time:O(n), Space:O(1)
public int removeDuplicates(int[] nums)
{
     // valid the input
     if (nums == null || nums.length == 0)
     {
        return 0;
     }
     // NOTE: no duplicate can happen
     if ( nums.length < 2)
     {
        return nums.length;
     }
     

     int last = 0; //int lastElement = nums[0];
     int cur = 1;
     //for (int i = 1 ; i < nums.length -1; i++ )
     while (cur < nums.length )
     {
          //if ( nums[cur] == lastElement)
          if ( nums[cur] == nums[last] )
          {
              cur++;
          }
          else 
          {   
              last++;
              nums[last] = nums[cur];
              cur++;
          }
     }
     // NOTE: last+1 since last is index and so length should be plus 1
     return last+1;
}
int countDup = 0;
for (i=0; i < len-1;i++)
{
   if ( nums[i] == nums[i+1])
    countDup++;
}
return A.length - countDup;
3. Similar Ones
[Array] Remove Duplicates from sorted array II

No comments:

Post a Comment