双指针算法解决移动零和复写零问题

本文主要是介绍双指针算法解决移动零和复写零问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨
🐻强烈推荐优质专栏: 🍔🍟🌯C++的世界(持续更新中)
🐻推荐专栏1: 🍔🍟🌯C语言初阶
🐻推荐专栏2: 🍔🍟🌯C语言进阶
🔑个人信条: 🌵知行合一
🍉本篇简介:>:讲解双指针算法解决移动零和复写零问题
金句分享:
✨相较于一见钟情,我更喜欢惊鸿一瞥.✨

前言

一、移动零

题目链接:传送门

题目描述:

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

注意要求:
必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

🍟解题思路:

本篇文章使用双指针算法解决,思路如下:
首先,虽然叫"双指针",但不一定非要是两个指针,这只是一种形象的说法,比如此题是数组,可以用两个整形变量作为下标.

创建一个"指针"cur,使其指向数组中第一个出现的0的位置.(如果数组中没有0,则直接返回).
创建第二个"指针" dest,从cur的下一个位置开始.
①如果dest指向的值是0,则继续dest继续往后遍历.
②如果dest指向的值是非0,则与cur进行交换.
当dest遍历结束,则完成要求.

我们这样操作可以将0都夹在cur和dest两个指针之间,最后dest指向最后,则0就全到数组最后面了.

图解:
在这里插入图片描述

🍔代码实现:

class Solution {
public:void moveZeroes(vector<int>& nums) {int sz=nums.size();  int cur=0; //cur指针指向数组中第一个0while(nums[cur]!=0 && cur!=sz-1){++cur;}if(cur==sz-1)return ;  //如果没有0,则直接返回//dest指针从cur指针的下一个开始int dest=cur+1;while(dest!=sz){if(nums[dest]!=0){       //如果这个数非0,则与cur交换          swap(nums[cur],nums[dest]);cur++;}++dest;}}
};

二、复写零

题目链接:传送门

题目描述:

给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

注意要求:
请不要在超过该数组长度的位置写入元素。请对输入的数组就地进行上述修改，不要从函数返回任何东西。

🍟解题思路:

如果我们直接从左往右开始复写,当遇到0,需要复写两次0的时候,会将后面的数字给覆盖掉.
在这里插入图片描述
我们采取从后往前覆盖的方法.

创建一个"指针"cur和一个"指针"dest.
cur指向最后一个需要复写的元素,dest指向复写后最后元素的位置.

那么如何找到这两个位置呢?

很简单,模拟一下复写过程即可.
cur往后遍历时,遇到非0,dest往后走一步.
遇到0,dest往后走两步.
当dest走到最后一个元素的时候,结束,此时cur和dest都到达了指定位置.

处理特殊情况:

出界原因:
由于dest可能一次跳2步,很可能从倒数第二个位置+2直接出界,此时需要特殊处理.

导致出界,说明当dest指向倒数第二个位置的时候,cur指向0,则表明最后一个位置应该设置为0.

在这里插入图片描述

处理方式:
①将最后一个元素复写为0 .
②dest-向左两步,指向倒数第二个位置.
③cur向前一步.

最后:从右往左遍历,完成正常的复写.

图解:
在这里插入图片描述

🍔代码实现

class Solution {
public:void duplicateZeros(vector<int>& arr) {int cur = 0, dest = -1;int sz = arr.size();//让cur指向最后一个复写的位置,dest指向完成复写后最后一个元素的位置while (dest < sz) {if (arr[cur] == 0) {dest+=2;}else ++dest;if (dest >= sz - 1)break;++cur;             }//处理特殊情况if (dest == sz) {arr[sz-1] = 0;dest-=2;--cur;}//从后往前复写while (cur >= 0) {if (arr[cur] == 0) {arr[dest--] = arr[cur];}arr[dest--] = arr[cur--];}}
};