LeetCode 283. 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.

解法一

思路

这题很简单，也有很多种写法，就看哪种写法更简洁了。这里我们采用从前向后的双指针法。

注意到“非0的数字”永远不可能向后移动，其只会向前移动或者原地不动，所以我们使指针i指向第一个值为0的元素（初始值为0，即指向第一个元素，注意这里并不要求其指向的元素值一定是0，只是说我们不能确定其一定不为0），然后指针j按顺序遍历数组，每当j指向的元素值不为0时，就给i指向的元素赋值为j指向元素的值，并且将i指针向后移动一位；知道j遍历完成后，这时就能确定i及i之后的元素值全都应该是0，所以给其后元素全部赋值0就好了。

拿示例[0, 1, 0, 3, 12]演示一遍：

0, 1, 0, 3, 12
^^
ij

0, 1, 0, 3, 12
^  ^
i  j

1, 1, 0, 3, 12
   ^  ^
   i  j

1, 1, 0, 3, 12
   ^     ^
   i     j

1, 3, 0, 3, 12
      ^     ^
      i     j

1, 3, 12, 3, 12
          ^     ^
          i     j

1, 3, 12, 0, 12
             ^  ^
             i  j

1, 3, 12, 0, 0
              ^ ^
              i j

output: [1, 3, 12, 0, 0]

Python

class Solution:
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        i = 0
        for num in nums:
            if num != 0:
                nums[i] = num
                i += 1
        while i < len(nums):
            nums[i] = 0
            i += 1

Java

public class Solution {
    public void moveZeroes(int[] nums) {
        int i = 0;
        for (int num : nums) {
            if (num != 0) {
                nums[i] = num;
                i++;
            }
        }
        while (i < nums.length) {
            nums[i] = 0;
            i++;
        }
    }
}

C++

class Solution {
public:
    void moveZeroes(vector<int> &nums) {
        int i = 0;
        for (auto num : nums) {
            if (num != 0) {
                nums[i] = num;
                i++;
            }
        }
        while (i < nums.size()) {
            nums[i] = 0;
            i++;
        }
    }
};