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

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

前言

一、移动零

题目链接:传送门

题目描述:

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

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

示例 1:

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

示例 2:

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

🍟解题思路:

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

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

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

图解:

🍔代码实现:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int sz=nums.size();  
        int cur=0; 

        //cur指针指向数组中第一个0
        while(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;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

二、复写零

题目链接:传送门

题目描述:

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

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

🍟解题思路:

如果我们直接从左往右开始复写,当遇到0,需要复写两次0的时候,会将后面的数字给覆盖掉.

我们采取从后往前覆盖的方法.

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

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

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

处理特殊情况:

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

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

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

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

图解:

🍔代码实现

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--];
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

这两道题目就讲到这里了,下次再见!