Move Zeros

[Leetcode] Move Zeroes, Solutions

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations. O(n)

Solution 1:

[Code]
void Solution(vector &nums)
{
     int len = nums.size();
     int zero = 0;
     int nz = 0;
     while(zero < len && nz < len) {
         if(nums[zero] != 0) {
             zero ++;
             nz = zero;
             continue;
         }
         if(nums[nz] == 0 ) {
             nz ++;
             continue;
         }
         swap(nums[zero], nums[nz]);
     }
}

Solution 2 : (shorter and elegant) 

[Code]
void Solution(vector &nums)
{
     int len = nums.size();
     int s = 0;  // slow pointer
     int f = 0;  // fast pointer
     while(f < len) {
         if(nums[f] != 0) { nums[s++] = nums[f++]; }
         else { f++; }
     } 
     while( s< len) { nums[s++] = 0; }
     }
}

Variety of extended problems:

1. Given an array nums, write a function to move all 0's to the beginning of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [0, 0, 1, 3, 12].

[Code]
void Solution(vector  &nums) 
{     
    int len = nums.size();
    int zero = len -1;
    int nz = len - 1;     
    while(zero >= 0 && nz >= 0) {
         if( nums[zero] != 0) {
             zero --;             
             nz = zero;             
             continue;         
         }         
         if (nums[nz] == 0) {
            nz --;
            continue;         
         }         
         swap(nums[zero], nums[nz]);     
    }
}

2. Given an array nums, write a function to move all  0 's to the beginning of it, order doesn't matter.

For example, given nums = [0, 1, 0, 3, 12],  after calling your function, nums should be [0, 0, 1, 3, 12].

[Code]
void Solution(vector  &nums)
{
    int len = nums.size();
     int zero = 0;
     int nz = 0;
     while(zero < len && nz < len) {
         if(nums[zero] != 0) {
            zero ++;
            continue;
         }
         if(nums[nz] == 0) {
            nz ++;
            zero = nz;
            continue;
         }
         swap(nums[nz], nums[zero]);
     }
}
  

3. Given an array nums, write a function to move all 0 's to the end of it, order doesn't matter.

For example, given nums = [0, 1, 0, 3, 12],  after calling your function, nums should be [1,3, 12, 0, 0].

[Code]
void Solution(vector  &nums)
{
     int len = nums.size();
     int zero = len -1;
     int nz = len -1;
     while(zero >=0 && nz >=0) {
        if(nums[zero] !=0) {
           zero --;
           continue;
        }
        if (nums[nz] ==0 ) {
            nz --;
            zero = nz;
            continue;
        }
       swap(nums[nz], nums[zero]);
     }
}

  

4. As you can see from the above problems, the concept of solution is to have two indices to make the element locations.
Let's investigate more about this,  Given an array nums, write a function to remove all 0 's to the end of it, and maintain the 
array order.

For example, given nums = [0, 1, 0, 3, 12],  after calling your function, nums should be [1,3, 12].

this is simple when you apply the index concept:

[Code]
int Solution(vector  &nums)
{
     int len = nums.size();
     int nozIndex = 0;
     for( int i= 0; i< len; i++) {
        if(nums[i] !=0) {
           s[nozIndex++] = s[i];
        }
     s.resize(nozIndex);
     return nozIndex;  // return the new size of the array
}

  

Please refer more about it from:

http://www.codepractices.com/2016/11/little-bit-about-quick-sort-quick-select.html