leetCode Question: Moving Zeros

Moving Zeros

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.

Analysis:
This is an easy problem and a simple for loop with two "pointers" will work well. Note that the problem requires the relative order.

The idea is to set two pointers, one for zeros, one for numbers (non-zero numbers), all start from 0, everytime we met zero value, then we swap the values of the pointers, and go to next value in the array. In this way, after a whole loop through the array, zeros are swapped into the end while the relative order of other numbers is stil kept.

Code (C++):

class Solution {

public:

void moveZeroes(vector<int>& nums) {

int j=0;

int tmp;

for (int i=0;i<nums.size();++i){

if (nums[i] != 0){

tmp = nums[i];

nums[i] = nums[j];

nums[j] = tmp;

j++;

}

}

}

};

Code (Python):

class Solution(object):

def moveZeroes(self, nums):

"""

:type nums: List[int]

:rtype: void Do not return anything, modify nums in-place instead.

"""

j=0

for i in range(len(nums)):

if nums[i] != 0:

nums[i], nums[j] = nums[j], nums[i]

j += 1