【leetcode】283. 移动零
题目内容
思路分析
本题和75. 颜色分类思想差不多。
方法一：双指针两次遍历
可以设置ptr指针，用来指示按原本的顺序排列的非0数。
第一次遍历：遇到非0数则对nums[ptr]赋nums[i]，同时将ptr+1。
第二次遍历：第一次遍历后，ptr以前的区域为按原本顺序排列好的非0数，因此只需要再遍历一遍，将ptr以后的区域全赋0就行了。
可以看参考资料2中的动图。
方法二：双指针一次遍历
可以设置ptr指针，用来指示按原本的顺序排列的非0数。
用i遍历数组，考虑以下情况：
- 当nums[i] == 0时，不做任何事情
- 当nums[i] != 0时，
- i == ptr，则当前i所指的数字在正确的位置上，故将ptr+1表示“原本的顺序排列的非0数”的范围扩大1
- i != ptr，则当前i所指的数字不在正确的位置上，需要将i与ptr所指的数字做交换，并将ptr+1表示“原本的顺序排列的非0数”的范围扩大1
由于i所经过的地方对非0数都做了交换操作，保证它们在正确的位置上，因此ptr与i之间的数字一定都是0（要么是交换过来的0要么是原本那个位置就是0）。也就是说当遍历结束时，ptr之前都是“原本的顺序排列的非0数”，ptr之后都是0。
可结合资料1和资料2理解。
代码
#include <vector>
#include <math.h>
#include <limits.h>
using namespace std;
// 双指针两次遍历
// 时间复杂度O(n)
// 空间复杂度O(1)
class Solution1 {
public:
void moveZeroes(vector<int>& nums) {
int ptr = 0;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] != 0) {
nums[ptr] = nums[i];
++ptr;
}
}
for (int j = ptr; j < nums.size(); ++j) {
nums[j] = 0;
}
}
};
// 双指针一次遍历
// 时间复杂度O(n)
// 空间复杂度O(1)
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int ptr = 0;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] != 0) {
//swap(nums[ptr++], nums[i]);
// 下面是对上面的优化
if(i > ptr) {
nums[ptr] = nums[i];
nums[i] = 0;
}
ptr++;
}
}
}
};
int main() {
Solution s;
vector<int> input{ 1,2,3,4,5 };
s.moveZeroes(input);
}
收获
- 没有太多收获