专题1 - 双指针 - leetcode 283. 移动零

1. 283. 移动零

1. 题目详情

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。

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

示例 2:
输入: nums = [0]
输出: [0]

提示:
1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

进阶：你能尽量减少完成的操作次数吗？

1. 原题链接

leetcode 283. 移动零

2. 基础框架

● Cpp代码框架

class Solution {
public:
    void moveZeroes(vector<int>& nums) {

    }
};

2. 解题思路

1. 题目分析

$(1)$ 题目要求把数组中所有的0移动到末尾，且数组中非零元素相对顺序不变，且原地对数组进行操作，不使用额外空间。

2. 算法原理 - 双指针

$(1)$ 本题使用双指针算法，指针指向dest表示非零元素的最后一个位置，指针cur从前向后遍历数组nums的每一个元素；所以dest就把数组分成了两个部分：[0,dest]表示非零元素序列，[dest+1, n-1]表示未处理区域。初始数组元素均未被处理，所以设置dest=-1，cur=0。初始非零元素序列[0,-1]即不存在，未处理区域[0, n-1]。
$(2)$ 如果nums[cur] != 0，是非零元素，让dest++，swap(nums[dest], nums[cur]),cur++;
否则就cur++。

3. 时间复杂度

$O(n)$

指针cur遍历一遍数组就完成了0元素的移动操作。

3. 代码实现

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int dest = -1, cur = 0;
        while(cur < nums.size()){
            if(nums[cur] != 0){
                swap(nums[++dest], nums[cur]);
            }
            cur++;
        }
    }
};

4. 知识与收获

$(1)$ 本篇是双指针专题的一道题目。对于数组问题，一般都会涉及到对数组的划分，至于是怎样划分与具体的题目有关。为什么要进行数组划分？进行数组划分把数组主观分成几个区域，对整体问题的处理分成了分别对几个区域的处理。
$(2)$本题中把数组分成了两部分：已被处理的区域即非零区域和未被处理的区域。通过对未被处理的区域内元素进行判定直到未处理区域没有元素，答案也就出来了。

---

$The$ $End$

原文地址：https://blog.csdn.net/weixin_64904163/article/details/136523084

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！