代码随想录-06-移除元素-283.移动零

目录

• 前言
• • 题目
  • 1. 双指针法
  • 2. 本题思路分析：
  • 3. 算法实现
  • 4. 算法分析
  • 5. 算法坑点

前言

在本科毕设结束后，我开始刷卡哥的“代码随想录”，每天一节。自己的总结笔记均会放在“class="superseo">算法刷题-代码随想录”该专栏下。
力扣此题链接

题目

给定一个数组 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. 双指针法

双指针法在数组和链表、字符串中的 *** 作非常常见。特别是题目所说，必须在不复制数组的情况下原地对数组进行 *** 作，使用双指针法。

2. 本题思路分析：

思路：
有两个int类型变量分别作为快慢指针，快指针每次循环时都向后移动一位，若此次循环快指针指向非0元素,则把当前快指针指向元素的值赋值给慢指针所在位置的元素（也就是说：当前快指针所指元素为非0元素，慢指针遇到0元素就会停止，此时把快指针与慢指针的值进行交换（而不是像之前一样快指针内容直接替换慢指针，因为此题需要保证末尾的0元素存在）)。
这就相当于，快指针充当循环的指针(类似循环中常用的int i)，而慢指针用于标记值为0的位置，当遇到值为0的元素慢指针就会停下，等待快指针遇到非0的元素，将快指针指向元素的值替换慢指针指向元素的值，并让慢指针向后移动一位。
举例
当遇到一个元素a的值为0，慢指针就会停下（因为需要标记这个位置，这个位置是需要等待替换的），快指针则会继续循环遍历，之后如果找到一个元素值非0的元素b，将元素b的值替换元素a的值，此时慢指针才可以后移一位。

3. 算法实现

• 代码：

#include
#include
using namespace std;
void moveZeroes(vector<int>& nums) {
        //双指针法
        //slow当遇到0时等待,当fast遇到非0值时与slow值交换,并且此时slow往后移动一位
        //并且要管末尾0,所以不能是简单的替换，而是要值为0的元素与值非0的元素进行交换
        int slow = 0,temp = 0;
        for(int fast = 0;fast < nums.size();fast++){
            if(nums[fast] != 0){
                temp = nums[fast];
                nums[fast] = nums[slow];
                nums[slow++] = temp;
            }
        }        
    }

4. 算法分析

n为数组长度
时间复杂度：O(n)
空间复杂度:O(1)

5. 算法坑点

• 移到末尾值为0的元素也需要保证存在：每次快慢指针的值应该是进行交换，而不是直接让快指针的元素替换慢指针元素的值。