前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >第一道完全是自己写出来的算法题!

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

作者头像
五分钟学算法
发布2023-01-10 08:53:18
1890
发布2023-01-10 08:53:18
举报
文章被收录于专栏:五分钟学算法五分钟学算法

一、题目描述

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

请注意 ,必须在不复制数组的情况下原地对数组进行操作。

示例 1:

代码语言:javascript
复制
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

代码语言:javascript
复制
输入: 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 就行。

三、参考代码

代码语言:javascript
复制
// 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)。只需要常数的空间存放若干变量。
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2022-11-21,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 五分钟学算法 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、题目描述
  • 二、题目解析
  • 三、参考代码
  • 四、复杂度分析
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档