Leetcode ： 移动零

时间：2024-03-01 09:08:42

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

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

思路：遍历数组元素，判定为0，则采用erase从数组删除，然后push_back在结尾补回来，也可以counter计数有多少0，最后统一处理；

！！！切记，判定为0后i--，边界也要减减，不然会死循环

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int noneZeroCount = nums.size();
        for (int i = 0; i < noneZeroCount; i++) {
            if (nums[i] == 0) {
                nums.erase(nums.begin() + i);
                nums.push_back(0);
                i--; // 处理可能删除元素导致的索引变化
                noneZeroCount--; // 处理可能插入新元素导致的索引变化
            }
        }
    }
};

int main() {
    Solution s;
    vector<int> nums = {0, 0, 1};
    s.moveZeroes(nums);
    for (auto i : nums)
        cout << i << " ";
    cout << endl;
    return 0;
}
思路： 也可以采用冒泡排序的方法，遇到0就与后一个元素进行交换，直至循环结束。可以设置交换的sign，默认置为false，如果存在交换则true，一次遍历后如果依然是false则表示遍历的子数组中不含0元素，都在末尾了。

#include <iostream>
#include <vector>

using namespace std;

// class Solution {
// public:
//     void moveZeroes(vector<int>& nums) {
//         int noneZeroCount = nums.size();
//         for (int i = 0; i < noneZeroCount; i++) {
//             if (nums[i] == 0) {
//                 nums.erase(nums.begin() + i);
//                 nums.push_back(0);
//                 i--; // 处理可能删除元素导致的索引变化
//                 noneZeroCount--; // 处理可能插入新元素导致的索引变化
//             }
//         }
//     }
// };

// 冒泡排序

class Solution {
    public:
    void moveZeroes(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            bool reverse = false;
            for (int j = 0; j < nums.size() - i - 1; j++){
                if (nums[j] == 0) {
                    swap(nums[j], nums[j + 1]);
                    reverse = true;
                }
            }
            if (!reverse) break; // 最后一次交换后，数组已经有序，提前退出
        }
    }
};

int main() {
    Solution s;
    vector<int> nums = {0, 0, 1};
    s.moveZeroes(nums);
    for (auto i : nums)
        cout << i << " ";
    cout << endl;
    return 0;
}

相关文章