南京建站软件,简历模板文档,云南建设投资集团网站,西宁市城北区建设网站一、题目描述
283. 移动零 - 力扣#xff08;LeetCode#xff09;
给定一个数组 nums#xff0c;编写一个函数将所有 0 移动到数组的末尾#xff0c;同时保持非零元素的相对顺序。
请注意 #xff0c;必须在不复制数组的情况下原地对数组进行操作。 二、题目解析
可以…一、题目描述
283. 移动零 - 力扣LeetCode
给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。
请注意 必须在不复制数组的情况下原地对数组进行操作。 二、题目解析
可以将本题划分为数组划分数组分块的一类题。
一般这类题可以运用双指针的思路去解决。
注意这里的指针并不是真正的指针而是利用数组下标来充当指针。
两个指针的作用
cur从左到右扫描数组遍历数组dest已经处理的区间内非零元素的最后一个位置所以初始要置为-1
所以这两个指针可以把数组分为三个区间 那这两个指针是如何做到的呢
cur从前往后遍历的过程中
遇到0元素cur遇到非零元素
swapdest1cur然后dest和cur分别继续遍历。
注意快排中的双指针算法也是运用这一思想
三、原码
void moveZeroes(int* nums, int numsSize) {//经典双指针算法int cur 0;int dest -1;for(cur 0;cur numsSize;cur){if(nums[cur] ! 0){int tmp nums[dest1];nums[dest1] nums[cur];nums[cur] tmp;dest;}}
}
四、复杂度
本题运用了双指针的算法时间复杂度是O(N)因为cur指针遍历数组一遍就已经按照题目要求排好序了。
空间复杂度是O(1)本题没有额外开辟数组空间。
总结双指针算法解决数组数组划分问题无论是时间复杂度还是空间复杂度算法都是最优的
