一、题目描述
给定一个数组 nums
,编写一个函数将所有 0
移动到数组的末尾,同时保持非零元素的相对顺序。
请注意 ,必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
提示:
-
1 <= nums.length <= 10^4
-
-2^31 <= nums[i] <= 2^31 - 1
进阶:你能尽量减少完成的操作次数吗?
二、题目解析
这题难度属于简单题,有很多小伙伴之前没有做过算法题都能第一遍独立做出来,相信你也可以的。
如果没有头绪的话,可以看看如下的动画描述和解析。
1、设置一个变量 slow,用来指向经过一系列操作后数组中所有为 0 元素的第一个位置上,一开始默认在索引为 0 的位置。
2、接下来,从头到尾遍历数组,遍历过程中使用变量 fast 指向对应的元素,遍历完毕之后,slow 指向了一个为 0 的元素,或者如果数组中不存在 0 ,就和 fast 一样,超过了数组的范围。
3、在遍历过程中,如果发现访问的元素是非 0 元素,说明 slow 不在正确的位置上,需要向后移动,寻找合适的位置。
4、执行的操作就是原先 slow 的值需要被 fast 的值覆盖, slow 需要向后移动,寻找合适的位置。
5、最终遍历结束后,只需要把 slow 极其后面所有的元素都设置为 0 就行。
三、参考代码
// LeetCode 100 题精讲:https://www.algomooc.com
// 作者:程序员吴师兄
// 移动零(LeetCode 283):https://leetcode.cn/problems/move-zeroes/
class Solution {
public void moveZeroes(int[] nums) {
// 设置一个变量,用来指向经过一系列操作后数组中所有为 0 元素的第一个位置上
// 一开始默认在索引为 0 的位置
int slow = 0;
// 从头到尾遍历数组
// 遍历完毕之后,slow 指向了一个为 0 的元素,或者如果数组中不存在 0 ,就和 fast 一样,超过了数组的范围
for (int fast = 0; fast < nums.length; fast++) {
// 在遍历过程中,如果发现访问的元素是非 0 元素
// 说明 slow 不在正确的位置上,需要向后移动,寻找合适的位置
if (nums[fast] != 0) {
// 这个时候,原先 slow 的值需要被 fast 的值覆盖
nums[slow] = nums[fast];
// slow 需要向后移动,寻找合适的位置
slow++;
}
}
// 接下来,只需要把 slow 极其后面所有的元素都设置为 0 就行
for (int i = slow; i < nums.length; i++) {
// 都设置为 0
nums[i] = 0;
}
}
}
四、复杂度分析
-
时间复杂度:O(n),其中 n 为序列长度。每个位置至多被遍历两次。 -
空间复杂度:O(1)。只需要常数的空间存放若干变量。
专栏包含哪些内容呢?
1、会交付 100 道 LeetCode 高频算法原题的动画讲解分析,同时提供 Java、Python、C++ 三种编程语言的代码。
以下为课程大纲和目录
2、每道算法题都提供动画讲解分析,相信我,哪怕是没有编程基础、纯小白、没刷过题的小伙伴都能看懂的。
3、每行代码都有注释,不用担心看不懂!
4、课程采取 Java 语言讲解,并提供 Java、Python、C++ 三大主流语言解法答案。
更多内容请点击下方图片查看。