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

题目解析

题目链接：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
  

1. `void swap(int*nums,int a,int b)
2. {
3.     int tmp=0;
4.     tmp=nums[a];
5.     nums[a]=nums[b];
6.     nums[b]=tmp;
7. }
8. void moveZeroes(int* nums, int numsSize) {
9.     int n=numsSize;
10.     int dest=-1;
11.     for(int cur=0;cur<numsSize;cur++)
12.     {
13.         if(nums[cur])
14.         {
15.             swap(nums,dest+1,cur);
16.             dest++;
17.         }
18.     }
19.    
20. }`

复制代码

• C++
  

1. `class Solution {
2. public:
3.     void moveZeroes(vector<int>& nums) {
4.         for(int cur=0,dest=-1;cur<nums.size();cur++)
5.         {
6.             if(nums[cur])
7.             {
8.                 swap(nums[++dest],nums[cur]);
9.             }
10.         }
11.         
12.     }
13. }；

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。