【蓝桥杯】每天一题，理解逻辑（1/90）【Leetcode 移动零】

IFMaxue

发布于 2025-02-27 08:50:47

1181

文章被收录于专栏：学习学习

题目解析

题目链接：https://leetcode.cn/problems/move-zeroes/description/

题目意思解析

把所有的零移动到数组的末尾
保持非零元素的相对顺序 理解了这两层的含义，这道题也就完成一半了。

讲解算法原理

解题思路：题目归类数组划分：将一个数组划分成若干个区间

解题方法：

【双指针算法思路】

(数组下标充当指针)

定义两个指针:dest，cur。

cur：从左往右扫描数组
dest：已处理区间内，非零元素的最后一个一个位置作用：两个指针可以划分成三个区间
(0,dest) ：非0区间
(dest+1,cur-1)：0区间
(cur,n-1)：待处理区间

如何划分和执行

cur初始化0，dest初始化-1
cur从左向右遍历，遇到0元素不做处理，遇到非0元素时，让dest+1，然后非零元素与dest所指元素进行交换（将非零元素直接归类到【0，dest】）

cur遍历到n-1时，结束

过程大致

联想思想：快排

cur指针先行遍历寻找非零元素
- 零元素：不做处理，往后遍历
- 非零元素：让dest++,然后dest所指向元素和cur元素进行交换
当cur遍历到数组末尾时候，结束。

代码详情

C

`void swap(int*nums,int a,int b)
{
    int tmp=0;
    tmp=nums[a];
    nums[a]=nums[b];
    nums[b]=tmp;
}
void moveZeroes(int* nums, int numsSize) {
    int n=numsSize;
    int dest=-1;
    for(int cur=0;cur<numsSize;cur++)
    {
        if(nums[cur])
        {
            swap(nums,dest+1,cur);
            dest++;
        }
    }
    
}`

C++

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-02-26，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历