算法学习之移动零

题目要求:

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:

必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/move-zeroes

解题代码：

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    // 时间复杂度：O(n)
    // 空间复杂度：O(n)
    void moveZeroes(vector<int>& nums) {
        vector<int> nonZeroElements;
        // 提取非零的元素
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i])
                nonZeroElements.push_back(nums[i]);
        }

        // 将非零的元素按顺序赋值给原有的数组
        for (int i = 0; i < nonZeroElements.size(); i++)
            nums[i] = nonZeroElements[i];

        // 将其他元素的值修改为0
        for (int i = nonZeroElements.size(); i < nums.size(); i++)
            nums[i] = 0;
    }
};

int main() {
    int arr[] = {0, 1, 0, 3, 12};
    vector<int> vec(arr, arr + sizeof(arr)/ sizeof(int));

    Solution().moveZeroes(vec);

    for (int i = 0; i < vec.size(); i++)
        cout<<vec[i]<<" ";
    cout<<endl;

    return 0;
}

不使用中间变量的解法：

class Solution {
public:
    // 时间复杂度：O(n)
    // 空间复杂度：O(1)
    void moveZeroes(vector<int>& nums) {

        int k = 0; // nums中，[0....k)的元素为非0元素

        // 遍历到i个元素，保证[0....i]中所有非0元素都按照顺序排列在[0...k)中
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i])
                nums[k++] = nums[i];
        }

        // 将nums剩余的位置设置为0
        for (int i = k; i < nums.size(); i++) {
            nums[i] = 0;
        }
    }
};

一次循环解决问题：

class Solution {
public:
    // 时间复杂度：O(n)
    // 空间复杂度：O(1)
    void moveZeroes(vector<int>& nums) {

        int k = 0; // nums中，[0....k)的元素为非0元素

        // 遍历到i个元素，保证[0....i]中所有非0元素都按照顺序排列在[0...k)中
        // 同时，[k....i] 为0
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i]) {
                if (i != k)
                    swap(nums[k++], nums[i]); // nums[k]与nums[i]进行值的交换
                else
                    k++;
            }
        }
    }
};