Wednesday, September 30, 2015

Leetcode: Move Zeroes

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.
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
Understand the problem:
Since the problem requires to maintain the relative order of the array, we cannot simply swap the numbers in the array. 

One simple way is very similar to remove the duplicated numbers in the array. In the first pass, we move all the non-zero elements upfront and fill out all the zero slots. Then we just need to append 0s at the end of the array.

Code (Java):
public class Solution {
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        
        int i = 0;
        int j = 0;
        
        // Step 1: compress the nums array by filling out the 0s
        while (i < nums.length) {
            if (nums[i] != 0) {
                nums[j] = nums[i];
                j++;
                i++;
            } else {
                i++;
            }
        }
        
        // Append 0s to the end
        while (j < nums.length) {
            nums[j] = 0;
            j++;
        }
    }
}

No comments:

Post a Comment