leetcode283：移动零

题目链接

leetcode

题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

/*
    双指针
    
    一个指针记录当前非零元素的位置，另一个指针遍历数组。
    遍历数组过程中，根据当前数字来判断：
        若非 0，则将非零数与当前指针指向的零数交换，并将指针右移。
        若是 0，则指针不动。
    最后，将数组 [0, right) 的元素设置为 0。

    时间复杂度：O(n)
        其中 n 为数组长度。
    空间复杂度：O(1)
*/
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int right = 0; // [0, right) 内的元素都不是 0
        for (const int& num : nums) {
            if (num != 0) {
                nums[right++] = num;
            }
        }
        
        for (int i = right; i < nums.size(); i++) {
            nums[i] = 0;
        }
    }
};

/*
    思路同上，遍历一次

    时间复杂度：O(n)
    空间复杂度：O(1)
*/
class Solution_1 {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        int left = 0, right = 0;

        while (right < n) {
            if (nums[right] != 0) {
                swap(nums[left], nums[right]);
                left++;
            }
            right++;
        }
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

int main() {
    Solution solution;
    vector<vector<int>> nums_cases = {
        {0,1,0,3,12},
        {0}
    };
    
    for (auto& nums : nums_cases) {
        cout << "Input: ";
        printArray(nums);

        solution.moveZeroes(nums);
        cout << "Output: ";
        printArray(nums);
    }
    
    return 0;
}