283. 移动零
一句话套路快慢指针:非零元素往前搬
题目描述
给定一个数组 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 开始)
逐帧动画
1 / 6
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
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;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
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});