LeetCode第283题：

github地址

有梦想的电信狗

前言

本文用C++实现 LeetCode 第283题

题目描述

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

在这里插入图片描述

题目与思路分析

目标分析：

将数组中所有的0移动到数组的末尾，同时保持非零元素的相对位置
不复制数组，即原地移除，意味着时间复杂度为O(n)，空间复杂度为O(1)
直接对原数组进行操作

思路：双指针

cur：用于扫描元素，从待扫描元素的第一个开始，因此初始下标为0
dest：指向数组中，已处理的区间中，最后一个非零元素的下标，初始时还未处理，**初始下标为-**1

操作：

cur < nums.size()时，进入循环判断
nums[cur] == 0 时：当前位置为0，cur++，略过该位置的元素0，dest不变
nums[cur] != 0 时：由于dest为已处理的区间中，最后一个非零元素的下标，因此dest++后指向下一个位置，再将非零元素nums[cur]与nums[dest] 交换，再cur++
- 即遇到非零元素：
  - ++dest
  - std::swap(nums[cur], nums[dest]);
  - ++cur

在这里插入图片描述

代码实现

时间复杂度：O(n)
空间复杂度：O(1)

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

算法代码优化

利用前置和后置++的特性最终优化，但不推荐这么写，因为算法的可读性下降了

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