建电商网站要多少钱,基础网站开发,文本编辑器 网站,百度做推广一般要多少钱Problem: 283. 移动零 文章目录 思路算法图解分析复杂度Code 思路 首先我们来讲一下本题的思路 本题主要可以归到【数组划分/数组分块】这一类的题型。我们将一个数组中的所有元素划分为两段区间#xff0c;左侧是非零元素#xff0c;右侧是零元素 那解决这一类的题我们首先想… Problem: 283. 移动零 文章目录 思路算法图解分析复杂度Code 思路 首先我们来讲一下本题的思路 本题主要可以归到【数组划分/数组分块】这一类的题型。我们将一个数组中的所有元素划分为两段区间左侧是非零元素右侧是零元素 那解决这一类的题我们首先想到的就是【双指针算法】学习过C语言的同学应该就可以知道指针是比较繁琐和复杂如果有兴趣学习的同学可以看看我的这篇文章 链接不过在这里呢我们不需要去使用int*这种指针而是直接使用数组下标来充当指针即可 好那我们就来看看这个双指针到底是怎样的要如何去使用 两个指针的作用 【cur】 从左往右扫描数组遍历数组【dest】已处理的区间内非零元素的最后一个位置 可以看到cur是我们用来遍历数组的从[cur, n - 1]就是还未处理的元素那么从[0, cur]就是已经处理过的元素但是呢本题的要求是我们要划分出【零元素】与【非零元素】所以呢前面的区间我们可以再度划分为[0, dest]和[dest 1, cur - 1] 小结一下
[0, dest] [dest 1, cur - 1] [cur, n - 1]
[0, dest] —— 非零元素[dest 1, cur - 1] —— 零元素[cur, n - 1] —— 未处理元素
算法图解分析 接下去我们就通过画算法图解的形式来模拟一下解题的过程 我们就以题目中所给出的第一个示例为例来进行讲解因为在一开始我们还没处理过任何的非零元素所以对于[0, cur - 1]这段区间是没有任何数据的所以在一开始我们可以将【dest】这个指针置于-1的位置 因为我们需要将非0元素移动到前面所以呢如果遇到了0元素的话cur即可将其留在这个位置上 那当我们遇到非0元素时就需要将其交换到前面去那我们[0, dest]这个区间就是用来存放非0元素的此时多了一个元素的话那dest就要加1原本其是指向-1这个位置那我们可以使用dest来完成 接下去当数据交换过来后我们可以去对照上面的这三个区间可以发现最左侧是非0元素中间是0元素右侧呢则是待处理的元素。接下去我们又碰到了0元素所以cur cur再后移之后呢我们又碰到了非0元素继续让dest上来然后交换二者位置上的元素 那现在我们再来看这三个区间左侧还是保持为【非0元素】中间为【0元素】右侧的话则是【待处理的元素】 然后碰到非0元素后继续让dest然后做交换 最后的话我们来看看这个处理完后的整个区间元素非0元素都在前面而0元素则都在后面[cur, n - 1]的这段区间也不存在了说明已经没有待处理元素了 复杂度 接下去我们来分析一下本题的时空复杂度 时间复杂度: 本算法的核心思路参考的是【快速排序】的区间划分我们这里就是在不断遍历数组的过程中以中间的0作为分割然后左侧是非0元素右侧是未处理的元素。在处理的过程中我们只是遍历了一次这个数组所以复杂度为 O ( n ) O(n) O(n) 空间复杂度: 在本题中我们并没有去开出额外的空间所以复杂度为 O ( 1 ) O(1) O(1) Code
class Solution {
public:void moveZeroes(vectorint nums) {for(int dest -1, cur 0; cur nums.size(); cur){if(nums[cur] ! 0){swap(nums[dest], nums[cur]);}}}
};
