Leetcode 每日一题4 Move Zeroes

题意

题目链接：Move Zeroes

给一个数组，通过交换将所有非零元素放置在前面，将所有零元素放置在后面。

要求In-place，即不能使用额外的空间存放数组元素。

另外还要求交换次数最少。

思路

为了满足题目要求，我们可以使用双指针法，找到一个零元素，以及在它后面的非零元素，将两者交换，不断重复这个过程。

假如不需要交换次数最少，有种更简洁的写法，即两次for循环，第一个for循环将非零元素放在数组前面，第二次for循环将非零元素放在数组后面。

代码

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int pZero = findNextZeroIndex(nums, -1);
        
        int pNonZero = findNextNonZeroIndex(nums, pZero);
        
        while (pZero < nums.size() && pNonZero < nums.size()) {
            swap(nums[pNonZero], nums[pZero]);
            pZero = findNextZeroIndex(nums, pZero);
            pNonZero = findNextNonZeroIndex(nums, pZero);
        }
    }
    int findNextZeroIndex(vector<int> &nums, int pZero) {
        pZero++;
        while (pZero < nums.size() && nums[pZero] != 0) {
            pZero++;
        }
        return pZero;
    }
    int findNextNonZeroIndex(vector<int> &nums, int pNonZero) {
        pNonZero++;
        while (pNonZero < nums.size() && nums[pNonZero] == 0) {
            pNonZero++;
        }
        return pNonZero;
    }
};