心之所向便是光

Leetcode 283.移动零

  • 2021-08-05
  • 作者 Ender
  • 1150 字
  • 次阅读

题目描述：

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

示例:

1
2
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

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

链接：

https://leetcode-cn.com/problems/move-zeroes

题目分析

  我们可以使用一个数 zero 来记录 0 的个数，则可以根据这个数算出非 0 数应该移动到的位置，全部处理完之后将后面 zero 个数全部置为 0 就可以。因为题目说尽量减少操作次数，因此我们增加了两条判断（第 9 行和第 14 行），如果是无需改变的就保持不动，而不是用原数字覆盖。
  写完了之后发现我们也可以记录非零数的个数，甚至都用不到减法，我真傻，真的。然后看了官方题解，使用的是双指针的做法，都知道后面全为 0 了还交换啥呢，直接覆盖最后再补 0 操作次数更少才对。然后好像别人写的是没有增加这两条判断的，我不管，我就是要满足操作次数最少！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int zero = 0;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] == 0){
                zero++;
            }
            else if(zero != 0){
                nums[i-zero] = nums[i];
            }
        }
        for(int i = nums.size() - zero; i < nums.size(); i++){
            if(nums[i] != 0){
                nums[i] = 0;
            }
        }
        return;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 是数组的大小。每个位置最多被遍历两次（扫描一次，覆盖一次）。
  空间复杂度：$O(1)$。原地算法，只需要常数个变量的空间。

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
,
最后编辑：2021-08-06