移动零
题目 移动零
思路分析
快排的思路 不过现在是同方向移动
指针i去找非0数 指针j找0
若j<i就交换(0在非0左边 交换)
若j<i(0在当前的非0右边 不交换 改变i状态 找下一个非0)
这样走到结尾就能使0全在最后
有个很牛的优化 本质也是0和非0交换
滚雪球
第一步 - 遇到 0。
现在的雪球的大小是 1。再进一步。
下一步 - 遇到 1。将雪球最左边的 0 与元素 1 交换。
下一步——再次遇到0
雪球球变大了，现在它的大小 = 2。
下一步 - 3. 再次与最左边的零交换。
看起来就是零一直在滚动
下一步 - 12. 再次交换：
到达终点
过程中只需要一个指针探 第二个指针直接等于第一个指针减去雪球大小即可
若出现非0 就做交换
代码实现
快排思路
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int i=0,j=0;
int n=nums.size();
while(i<n && j<n)
{
//i找非0数
while(i<n && nums[i]==0){
i++;
}
//j找0
while(j<n && nums[j]!=0){
j++;
}
if(i<n && j<n)
{
//如果0在非0左边 交换
if(j<i)
swap(nums[i],nums[j]);
//如果0在当前的非0右边 不需要交换 找下一个非0数（改变i的状态）
else
i++;
}
}
}
};
滚雪球
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int snowball=0;
for(int i=0;i<nums.size();i++)
{
if(nums[i]==0)
snowball++;
else if(nums[i]!=0 && snowball>0)
{
swap(nums[i],nums[i-snowball]);
}
}
}
};
💬 评论