283 移动零
本人思路
Leetcode的思路不方便把题目串在一起,本题最好的思路我认为是:
借鉴于数组移除元素的思路
本题移动零本质上就是分为两步:
- 把数组中等于0的元素移除,也就是数组移除元素中val == 0的情况
- 得到非零元素长度为len后,把数组末尾的元素赋值为0
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int slow = -1, fast = 0;
while(fast < nums.size()){
if(nums[fast] != 0){
slow++;
nums[slow] = nums[fast];
}
fast++;
}
fast = slow + 1;
while(fast < nums.size()){
nums[fast] = 0;
fast++;
}
}
};
Leetcode思路
暴力解法
题目要求:
- 将所有的零移动到数组的末尾,且不改变非零元素的顺序
- 在原地对数组进行操作
思路:
- 题目要求在原地对数组进行操作,那我们就假设[0, k - 1]都是非零元素,[k, n - 1]都是零
- 遍历数组,通过
nums[i] == 0找到第一个零元素 - 移动到数组的末尾:
for (int j = i + 1; j < n; j++)我们可以往后找到非零元素,将其与零元素交换,那么就可以保证数组前面都是零元素
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; i++) {
if (nums[i] == 0) {
for (int j = i + 1; j < n; j++) {
if (nums[j] != 0) {
swap(nums[i], nums[j]);
// 保证非零元素的顺序,需要break
break;
}
}
}
}
}
};
双指针优化
我们发现暴力解法中,i指向第一个零元素的位置,j指向第一个非零元素的位置
j的遍历重复经过了[i, j]之间的多个零元素
因此可以使用双指针优化
=== "简洁版“
```C++
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size();
// l 指向第一个零元素
int l = 0;
// r指向第一个非零元素
for(int r = 0; r < n; r++){
if(nums[r] != 0){
swap(nums[l],nums[r]);
l++;
}
}
}
};
```