Wednesday, August 26, 2015

[Duplicate][Two Pointers] Remove Duplicates from Sorted Array II

1. Example
Allow one duplicate!
s= [1,1,1,2,2,3]
You should return length = 5
new s = [1,1,2,2,3]

2. Implementation
duplicate => hash
sorted array => duplicate next to each other
keep checking and replace the second(third here since it allow a duplicate) duplicate
with the next non-duplicate character
Q1: how to know duplicate happen?
A1: keep a index to point out where duplicate happen
Q1: how to know this is third duplicate and is not allowed?
A1: keep a index to point out where duplicate happen plus one flag to indicate this is first duplicate
. So when duplicate happen and firstDuplicate flag is true, we tend to replace this duplicate (record its index) with the next non-duplicate
Q1: Can we use the method by counting how many duplicate which is beyond two duplicate happen?
A1: we can do that by keep two pointers
NOTE:
when detect first duplicate happen, we see it as a non-duplicate and increment lastIndex value // 
NOTE: duplicate if ( nums.length < 2) { return nums.length; }



// Time:O(n), Space:O(1)

public int removeDuplicates(int[] nums)
{


    // validate the input
    // NOTE: duplicate
    if ( nums.length < 2)
    {
        return nums.length;
    }


 


    int lastIndex = 0;
    int iterIndex = 1;
    boolean firstDuplicate = fasle;
    while (   iterIndex < nums.length )
    {
          if (  nums[lastIndex] == nums[iterIndex]  ) 
          {
               if (!firstDuplicate)
               { 
                   lastIndex++;
                   firstDuplicate = true;
               } 
          }
          else 
          {
               lastIndex++;
               nums[lastIndex] = nums[iterIdnex];
               firstDuplciate = false;
          }
          iterIndex++;
    }

    return lastIdnex+1;
0 1 2 3 4 5
l i
1,1,1,2,2,3

i1  n[0]==n[1]
    fl= t 
    l++=> 1
    i++ => 2
i2  n[1]==n[2]
    i++= > 3
i3  n[1] != n[3]
    l++ => 2
    n[2] = n[3]
    i++ => 4
    fl = f
i4  n[2] = n[4]
    f1 = t 
    l++ =>3
    i++ =>5
i5  n[3] != n[5]
    l++ => 4
    n[4] = n[5]
    i++ => 6
    STOP
}
 int last = 1;
 int iter =2;
 while ( iter < nums.length )
 {
      if (nums[iter] == nums[last] && nums[iter]== nums[last-1])
          iter++
      else
      {
          last++;
          num[last] = num[iter];
          iter+=
      }
 }

 return last++;
3. Similar Ones
Remove Duplicate from Sorted Array

No comments:

Post a Comment