自己写通过的:
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int slow = 0, fast = 0;
while (fast < nums.size())
{
if (nums[slow] == 0 && nums[fast] != 0)
{
nums[slow] = nums[fast];
nums[fast] = 0;
}
if (nums[slow] != 0) slow ++;
fast ++;
}
}
};
基本思想就是在更换时一定是要nums[slow] == 0
和 nums[fast] != 0
同时满足,然后slow
查找值为0的位置,当找到值为0的位置时,就不动了,直到更换了两个数,导致这个slow
位置的数不为0,然后执行slow ++
,至于fast
则是从头到尾遍历整个数组,找出值不为0的位置,然后在nums[slow] == 0 && nums[fast] != 0
满足时,更换位置,注意每次while循环都要执行fast ++
。
然后就是在做这题的时候自己也踩了些坑,感觉还是有必要写下的:
第一个坑就是读题目的时候有点粗心,没看清楚全部要满足的条件,导致第一次写的时候写了如下代码:
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right)
{
if (nums[left] == 0)
{
nums[left] = nums[right];
nums[right] = 0;
right --;
}
else left ++;
}
}
};
这段代码虽然也能把所有 0 移动到数组的末尾,但是没有保持非零元素的相对顺序。
第二个坑就是有点想当然,直接把slow ++
放第一个if里面了,也就是如下代码:
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int slow = 0, fast = 0;
while (fast < nums.size())
{
if (nums[slow] == 0 && nums[fast] != 0)
{
nums[slow] = nums[fast];
nums[fast] = 0;
slow ++;
}
fast ++;
}
}
};
错误的原因就是认为当更换两个位置的数时,要让slow ++
,但是没考虑到当slow
对应的元素不为0时,也要让slow ++
,因为要让slow
位置的元素为0,等待right
位置的不为0的元素来进行交换。
再附上分析的两张图:
第二张图其实就是我踩的第二个坑的第一个不通过的案例
最后看了下官方题解,也有些收获
官方代码:
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size(), left = 0, right = 0;
while (right < n) {
if (nums[right]) {
swap(nums[left], nums[right]);
left++;
}
right++;
}
}
};
感觉官方思路是从一个更大的更宏观的角度去考虑的,刚开始并没有考虑left
,而是从right
出发,用right
来遍历整个数组,看right
位置的数值是不是不为0,如果不为0,则一定是放在前面的,也就是slow
位置,然后再slow ++
,来满足左指针左边均为非零数,同时为下个可能要更换的数做准备;