第一道完全是自己写出来的算法题!

一、题目描述

给定一个数组 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)。只需要常数的空间存放若干变量。



本题目的视频和动画版在专栏《玩转 LeetCode 高频 100 题》可以查看。

专栏包含哪些内容呢?

1、会交付 100 道 LeetCode 高频算法原题的动画讲解分析,同时提供 Java、Python、C++ 三种编程语言的代码。

以下为课程大纲和目录

第一道完全是自己写出来的算法题!

2、每道算法题都提供动画讲解分析,相信我,哪怕是没有编程基础、纯小白、没刷过题的小伙伴都能看懂的。

第一道完全是自己写出来的算法题!

3、每行代码都有注释,不用担心看不懂!

第一道完全是自己写出来的算法题!

4、课程采取 Java 语言讲解,并提供 Java、Python、C++ 三大主流语言解法答案

更多内容请点击下方图片查看。

第一道完全是自己写出来的算法题!