Monday, August 24, 2015

[Two Pointerss] Remvoe element

1. Example
a= [1,2,3,4,5,6] and removal value =3
a= [1,2,4,5,6]
Return 5 (new array length)

Thought1 count the one different from removal value
Time:(n), Space:O(1)

2. Implementation
// NOTE: increment => count different
 // NOTE: if keep array in order
 // NOTE: decrement => minus same
 // NOTE: i-- to remove current element
 // NOTE: swap current value with the last element of array

// Time :O(n), Space:O(1)
public int removeElement(int[] nums, int val)
{
     // validate the input
     if (nums == null || nums.length == 0)
     {
         return 0;
     }
     

     // NOTE: increment => count different
     int countNewLength =0;
     for (int i = 0; i < nums.length ; i++)
     {
           if (nums[i] != val)
           {
               // NOTE: if keep array in order 
               nums[countNewLength] = nums[i];
               countNewLength++;
           }
     }
     return countNewLength;
}
     // NOTE: decrement => minus same
     int len = nums.length-1;
     for (int i = 0 ; i < nums.length;i++)
     {
           if (nums[i] == val)
           {
               // NOTE: i-- to remove current element
               // NOTE: swap current value with the last element of array
               nums[i--] = nums[len--]; 
           }
     }    
     // NOTE: len +1 since len init as num.length-1 (index)
     return len+1;
3. Similar Ones
(E) Remove linked list elements

No comments:

Post a Comment