跳转至

283 移动零

本人思路

Leetcode的思路不方便把题目串在一起,本题最好的思路我认为是:

借鉴于数组移除元素的思路

本题移动零本质上就是分为两步:

  1. 把数组中等于0的元素移除,也就是数组移除元素中val == 0的情况
  2. 得到非零元素长度为len后,把数组末尾的元素赋值为0
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int slow = -1, fast = 0;
        while(fast < nums.size()){
            if(nums[fast] != 0){
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
        }
        fast = slow + 1;
        while(fast < nums.size()){
            nums[fast] = 0;
            fast++;
        }
    }
};

Leetcode思路

暴力解法

题目要求:

  1. 将所有的零移动到数组的末尾,且不改变非零元素的顺序
  2. 在原地对数组进行操作

思路:

  • 题目要求在原地对数组进行操作,那我们就假设[0, k - 1]都是非零元素,[k, n - 1]都是零
  • 遍历数组,通过nums[i] == 0找到第一个零元素
  • 移动到数组的末尾:for (int j = i + 1; j < n; j++)我们可以往后找到非零元素,将其与零元素交换,那么就可以保证数组前面都是零元素
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                for (int j = i + 1; j < n; j++) {
                    if (nums[j] != 0) {
                        swap(nums[i], nums[j]);
                        // 保证非零元素的顺序,需要break
                        break;
                    }
                }
            }
        }
    }
};

双指针优化

我们发现暴力解法中,i指向第一个零元素的位置,j指向第一个非零元素的位置

j的遍历重复经过了[i, j]之间的多个零元素

因此可以使用双指针优化

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int i = 0;
        if(nums[i] != 0)
            i++;
        for(int j = 1; j < nums.size(); j++){
            if(nums[j] != 0){
                swap(nums[i], nums[j]);
                i++;
            }
        }
    }
};

=== "简洁版“

```C++
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        // l 指向第一个零元素
        int l = 0;
        // r指向第一个非零元素
        for(int r = 0; r < n; r++){
            if(nums[r] != 0){
                swap(nums[l],nums[r]);
                l++;
            }
        }
    }
};
```