HHot 100C++ 图解

283. 移动零

简单 双指针 6 帧动画 在力扣上做

一句话套路快慢指针:非零元素往前搬

题目描述

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

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

 

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

 

提示:

  • 1 <= nums.length <= 104
  • -231 <= nums[i] <= 231 - 1

 

进阶:你能尽量减少完成的操作次数吗?

思路

时间O(n)
空间O(1)

思路

快慢指针。慢指针 k 始终指向「下一个非零元素该放的位置」,快指针扫完全程后,把 [k, n) 全部填 0。等价于 stable_partition。

图解

0 0 1 1 0 2 3 3 12 4
数组(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 6

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/02_two_pointers.cpp11 行
namespace lc0283 {
class Solution {
 public:
  void moveZeroes(vector<int>& nums) {
    int k = 0;
    for (int x : nums)
      if (x != 0) nums[k++] = x;
    while (k < (int)nums.size()) nums[k++] = 0;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q283_move_zeroes10 行
lc0283::Solution s;
vector<int> a{0, 1, 0, 3, 12};
s.moveZeroes(a);
CHECK_EQ(a, vector<int>{1, 3, 12, 0, 0});
vector<int> b{0, 0, 0};
s.moveZeroes(b);
CHECK_EQ(b, vector<int>{0, 0, 0});
vector<int> c{1, 2, 3};
s.moveZeroes(c);
CHECK_EQ(c, vector<int>{1, 2, 3});

↑↓ 选择↵ 打开/ 随时唤起