[双指针] Leetcode 283.移动零和1089.复写零
移动零
283. 移动零
1.题意分析
(1) 给你一个数组,将数组中的所有0移动到数组的末尾
(2) 保证非0元素在数组中相对位置不变
(3) 在原数组中操作
2.解题思路
由于题目要求我们移动数组内容(也就是交换两个数的位置),所以我们很容易想到双指针解法。
解法:双指针
定义两个“指针”(left 和 right),right遍历整个数组,遇到0就交换两个数的位置。
nums[right] == 0:right++;
nums[right] != 0:swap(nums[right], nums[left]), right++, left++
示例1:[0, 1, 0, 3, 12]
请先自己尝试实现代码,再来继续往下看。
3.代码实现
class Solution {
public:
void moveZeroes(vector<int>& nums) {
for(int left = 0, right = 0; right < nums.size(); )
{
if(nums[right] != 0) swap(nums[left++], nums[right++]);
else right++;
}
}
};
4.总结
细节1:right的大小由我们自己在if-else控制,并不需要写入循环。
细节2:right的大小超过数组的size即为遍历完整个数组。
复习零
1089. 复写零
1.题意分析
(1) 给你一个长度固定的数组,将数组中的0再次写一遍,即为在0后再加一个0
(2) 其余的数向右平移
(3) 超过数组长度,终止写入元素
(4) 在原数组上进行操作
2.解题思路
题目要求我们进行复写0,即需要知道两个数的位置,所以可以使用两个“指针”,一前一后:判断0,添加0。
解法:双指针
由于数组空间是固定的,我们首先需要知道最后一个数的位置,然后倒着进行修改数组。
nums[i] == 0:count+= 2;
nums[i] != 0:count++;
count >= nums.size-1:break;
i++;
i即为新数组的最后一个数,我们在倒着写回数组。
nums[i] == 0:nums[count] = 0, count[count-1] = 0, i--, count -= 2;
nums[i] != 0:nums[count] = nums[i], i--, count--。
示例1:
nums[] = [1, 0, 2, 3, 0, 4, 5, 0]
注意处理这样的数组: nums[] = {8, 4, 5, 0, 0, 0, 0, 7}
请先自己尝试实现代码,再来继续往下看。
3.代码实现
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
//1.计算数组最后一个位置
int count = -1, i = 0, n = arr.size();
while(count < n)
{
if(arr[i] != 0) count++;
else count += 2;
if(count >= n-1) break;
i++;
}
//处理特殊情况
if(count == n)
{
arr[n-1] = 0;
i--;
count -= 2;
}
//2.逆向填充数组
while(i >= 0)
{
if(arr[i] != 0) arr[count--] = arr[i--];
else
{
arr[count--] = 0;
arr[count--] = 0;
i--;
}
}
}
};
4.总结
细节1:count为什么初始化为-1:因为数组下标是从0开始的,从-1开始可以和数组下标对应上,不会越界;从0开始最后又得减掉,后续处理十分麻烦。
细节2:求最后的复写数时,循环中if(count >= n-1) break;:如果此时count已经大过数组的size-1(也就是超出数组的范围),就没有必要再让当前的下标i再加1了。
细节3:nums[] = {8, 4, 5, 0, 0, 0
, 0, 7}:这样的数组,我们最后复写出来的结果为{8, 4, 5, 0, 0, 0, 0, 0}因为第三个0,会有一个0复写时越界了,我们之前的算法无法处理这种特殊情况,需要我们手动处理一下:count == nums.size时,将数组的最后一位手动赋值0,最后复写的数的下标i应该-1,而count应该-2(看不懂就画一下图)。文章来源:https://www.toymoban.com/news/detail-718476.html
END, THANKS。文章来源地址https://www.toymoban.com/news/detail-718476.html
到了这里,关于[双指针](一) Leetcode 283.移动零和1089.复写零的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!