LeetCode 283 Move 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:
You must do this in-place without making a copy of the array. Minimize the total number of operations.

Diffculty Easy

Similar Problems

Analysis

典型的双指针问题。使用两个指针遍历数组，一个指向数值为0的元素，另一个指向数值不为0的元素， 在遍历的过程中，不断交换两个指针的值。

i j              i j             i   j         i   j           i   j         i    j
0 1 0 3 12 -> 1 0 0 3 12 -> 1 0 0 3 12 -> 1 3 0 0 12 -> 1 3 0 0 12 -> 1 3 12 0 0

Solutions

class Solution {
public:
    void moveZeroes(vector<int>& A) {
        int n = A.size();
        for(int zero_index = 0, none_zero_index = 0; none_zero_index < n && zero_index < n;) {
            if(A[zero_index] != 0) {
                ++zero_index;
                none_zero_index = zero_index; // j 要保持 j > i, 所以这里要更新它
                continue;
            }

            if(A[none_zero_index] == 0) {
                ++none_zero_index;
                continue;
            }
            // 只有当zero_index 指向非零元素，并且none_zero_index指向零元素时，才进行交换
            int temp = A[zero_index];
            A[zero_index] = A[none_zero_index];
            A[none_zero_index] = temp;

            ++zero_index;
            ++none_zero_index;
        }
    }
};

Reference