Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >【算法千题案例】⚡️每日LeetCode打卡⚡️——51.移动零

【算法千题案例】⚡️每日LeetCode打卡⚡️——51.移动零

作者头像
呆呆敲代码的小Y
发布于 2021-10-13 03:30:02
发布于 2021-10-13 03:30:02
41500
代码可运行
举报
运行总次数:0
代码可运行


原题样例:移动零

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

示例:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
必须在原数组上操作,不能拷贝额外的数组。
尽量减少操作次数。

C#方法:排序

增加一个索引index,从0开始,当遍历数组的时候,如果数组当前位置不为0,则把当前的数值赋值给数组[index],然后index 自增1

如果当前位置不等于索引的位置(i 只能大于等于index),那么就把当前位置赋值为0,

此操作是为将数组后面的值变为0

代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
public class Solution {
    public void MoveZeroes(int[] nums) {
        int index =0;
        for(int i=0;i<nums.Length;i++){
            if(nums[i]!=0){
                nums[index] = nums[i];
                if(i!=index){
                    nums[i]=0;
                }
                index++;
            }
        }
    }
}

执行结果

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
通过
执行用时:152 ms,在所有 C# 提交中击败了98.73%的用户
内存消耗:51.5 MB,在所有 C# 提交中击败了5.06%的用户

Java 方法:双指针

思路解析 使用双指针,左指针指向当前已经处理好的序列的尾部,右指针指向待处理序列的头部。

右指针不断向右移动,每次右指针指向非零数,则将左右指针对应的数交换,同时左指针右移。

注意到以下性质:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
左指针左边均为非零数;

右指针左边直到左指针处均为零。

因此每次交换,都是将左指针的零与右指针的非零数交换,且非零数的相对顺序并未改变。

代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length, left = 0, right = 0;
        while (right < n) {
            if (nums[right] != 0) {
                swap(nums, left, right);
                left++;
            }
            right++;
        }
    }

    public void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

执行结果

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
通过
执行用时:2 ms,在所有 Java  提交中击败了21.64%的用户
内存消耗:39.9 MB,在所有 Java 提交中击败了5.01%的用户

复杂度分析

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
时间复杂度:O( n )
空间复杂度:O( 1 ) 

Java方法二:哈希表

我们可以直接查询每个数是否在数组中出现过来找出缺失的数字。如果使用哈希表,那么每一次查询操作都是常数时间的。

我们将数组中的所有数插入到一个集合中,这样每次查询操作的时间复杂度都是 O(1)的

代码

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
    public int missingNumber(int[] nums) {
        Set<Integer> numSet = new HashSet<Integer>();
        for (int num : nums) numSet.add(num);

        int expectedNumCount = nums.length + 1;
        for (int number = 0; number < expectedNumCount; number++) {
            if (!numSet.contains(number)) {
                return number;
            }
        }
        return -1;
    }
}

执行结果

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
通过
执行用时:5 ms,在所有 Java  提交中击败了33.30%的用户
内存消耗:38.9 MB,在所有 Java 提交中击败了26.29%的用户

复杂度分析

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
时间复杂度:O( n )
空间复杂度:O( n )

总结

  • 今天是力扣算法题打卡的第五十一天!
  • 文章采用 C#Java 两种编程语言进行解题
  • 一些方法也是参考力扣大神写的,也是边学习边分享,再次感谢算法大佬们
  • 那今天的算法题分享到此结束啦,明天再见!


本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021/10/11 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

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

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

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
【算法千题案例】⚡️每日LeetCode打卡⚡️——59.最大连续 1 的个数
????前言 ????原题样例:最大连续 1 的个数 ????C#方法:一次遍历 ????Java 方法:一次遍历 ????总结 ????前言 ???? 算法题 ???? ???? 每天打卡一道算法
呆呆敲代码的小Y
2021/10/22
3890
【算法千题案例】⚡️每日LeetCode打卡⚡️——52.两个数组的交集
---- 原题样例:两个数组的交集 给定两个数组,编写一个函数来计算它们的交集。 示例: 输入:nums1 = [1,2,2,1], nums2 = [2,2] 输出:[2] 示例 2: 输入:nu
呆呆敲代码的小Y
2021/10/15
4340
【小Y学算法】⚡️每日LeetCode打卡⚡️——25.二叉树的中序遍历
二叉树的中序遍历:按照访问左子树——根节点——右子树的方式遍历这棵树,而在访问左子树或者右子树的时候我们按照同样的方式遍历,直到遍历完整棵树。
呆呆敲代码的小Y
2021/09/08
2160
【算法千题案例】⚡️每日LeetCode打卡⚡️——53.两个数组的交集 II
使用Dictionary字典操作,先把第一个数组遍历进字典,然后再同第二个数组做判定即可!
呆呆敲代码的小Y
2021/10/15
3260
【小Y学算法】⚡️每日LeetCode打卡⚡️——26.相同的树
思路解析 如果两个二叉树都为空,则两个二叉树相同。如果两个二叉树中有且只有一个为空,则两个二叉树一定不相同。
呆呆敲代码的小Y
2021/09/08
2170
【小Y学算法】⚡️每日LeetCode打卡⚡️——17.最大子序和
本文章是⭐️小Y学算法⭐️的内容,该专栏还有多篇优质内容在等待你观看,现在点击右上角点击这个————????订阅专栏???? 就可以免费观看多篇相关内容的文章啦! ????前言 ????原题样例 ?
呆呆敲代码的小Y
2021/09/01
1970
【小Y学算法】⚡️每日LeetCode打卡⚡️——17.最大子序和
【小Y学算法】⚡️每日LeetCode打卡⚡️——16.搜索插入位置
思路解析 这道题跟上一篇的实现 strStr()挺相似的,都是给定一个目标值,返回索引
呆呆敲代码的小Y
2021/08/25
2270
【小Y学算法】⚡️每日LeetCode打卡⚡️——16.搜索插入位置
【小Y学算法】⚡️每日LeetCode打卡⚡️——28.二叉树的最大深度
具体而言,在计算当前二叉树的最大深度时,可以先递归计算出其左子树和右子树的最大深度,然后在 O(1) 时间内计算出当前二叉树的最大深度。递归在访问到空节点时退出。
呆呆敲代码的小Y
2021/09/10
2670
【小Y学算法】⚡️每日LeetCode打卡⚡️——28.二叉树的最大深度
【小Y学算法】⚡️每日LeetCode打卡⚡️——15.实现 strStr()
给你两个字符串 haystack和 needle,请你在 haystack 字符串中找出 needle字符串出现的第一个位置(下标从 0 开始)。
呆呆敲代码的小Y
2021/08/23
2630
【小Y学算法】⚡️每日LeetCode打卡⚡️——29.将有序数组转换为二叉搜索树
给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。
呆呆敲代码的小Y
2021/09/10
2570
【小Y学算法】⚡️每日LeetCode打卡⚡️——47.存在重复元素
如果存在一值在数组中出现至少两次,函数返回 true 。如果数组中每个元素都不相同,则返回 false
呆呆敲代码的小Y
2021/10/08
3790
【小Y学算法】⚡️每日LeetCode打卡⚡️——14.移除元素
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
呆呆敲代码的小Y
2021/08/23
3520
【算法千题案例】⚡️每日LeetCode打卡⚡️——50.丢失的数字
给定一个包含 [0, n] 中 n 个数的数组 nums ,找出 [0, n] 这个范围内没有出现在数组中的那个数。
呆呆敲代码的小Y
2021/10/13
3730
【算法千题案例】⚡️每日LeetCode打卡⚡️——54.第三大的数
---- 原题样例:. 第三大的数 给你一个非空数组,返回此数组中 第三大的数 。如果不存在,则返回数组中最大的数。 示例: 输入:[3, 2, 1] 输出:1 解释:第三大的数是 1 。 示例 2: 输入:[1, 2] 输出:2 解释:第三大的数不存在, 所以返回最大的数 2 。 示例3 输入:[2, 2, 3, 1] 输出:1 解释:注意,要求返回第三大的数,是指在所有不同数字中排第三大的数。 此例中存在两个值为 2 的数,它们都排第二。在所有不同数字中排第三大的数为 1 。 说明: 输出结果中
呆呆敲代码的小Y
2021/10/15
2880
【小Y学算法】⚡️每日LeetCode打卡⚡️——13.删除有序数组中的重复项
给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。
呆呆敲代码的小Y
2021/08/19
2450
【算法千题案例】⚡️每日LeetCode打卡⚡️——56.最小操作次数使数组元素相等
给你一个长度为n 的整数数组,每次操作将会使 n - 1个元素增加1。返回让数组所有元素相等的最小操作次数。
呆呆敲代码的小Y
2021/10/20
3860
【算法千题案例】⚡️每日LeetCode打卡⚡️——58.岛屿的周长
给定一个row x col的二维网格地图 grid,其中:grid[i][j] = 1表示陆地, grid[i][j] = 0 表示水域。
呆呆敲代码的小Y
2021/10/22
3350
【算法千题案例】⚡️每日LeetCode打卡⚡️——58.岛屿的周长
【数据结构和算法】移动零
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
绿毛龟
2024/01/19
1270
【数据结构和算法】移动零
【算法千题案例】⚡️每日LeetCode打卡⚡️——55.找到所有数组中消失的数字
给你一个含 n 个整数的数组 nums ,其中 nums[i] 在区间 [1, n] 内。
呆呆敲代码的小Y
2021/10/18
2710
【小Y学算法】⚡️每日LeetCode打卡⚡️——45.多数元素
给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
呆呆敲代码的小Y
2021/10/08
3200
推荐阅读
【算法千题案例】⚡️每日LeetCode打卡⚡️——59.最大连续 1 的个数
3890
【算法千题案例】⚡️每日LeetCode打卡⚡️——52.两个数组的交集
4340
【小Y学算法】⚡️每日LeetCode打卡⚡️——25.二叉树的中序遍历
2160
【算法千题案例】⚡️每日LeetCode打卡⚡️——53.两个数组的交集 II
3260
【小Y学算法】⚡️每日LeetCode打卡⚡️——26.相同的树
2170
【小Y学算法】⚡️每日LeetCode打卡⚡️——17.最大子序和
1970
【小Y学算法】⚡️每日LeetCode打卡⚡️——16.搜索插入位置
2270
【小Y学算法】⚡️每日LeetCode打卡⚡️——28.二叉树的最大深度
2670
【小Y学算法】⚡️每日LeetCode打卡⚡️——15.实现 strStr()
2630
【小Y学算法】⚡️每日LeetCode打卡⚡️——29.将有序数组转换为二叉搜索树
2570
【小Y学算法】⚡️每日LeetCode打卡⚡️——47.存在重复元素
3790
【小Y学算法】⚡️每日LeetCode打卡⚡️——14.移除元素
3520
【算法千题案例】⚡️每日LeetCode打卡⚡️——50.丢失的数字
3730
【算法千题案例】⚡️每日LeetCode打卡⚡️——54.第三大的数
2880
【小Y学算法】⚡️每日LeetCode打卡⚡️——13.删除有序数组中的重复项
2450
【算法千题案例】⚡️每日LeetCode打卡⚡️——56.最小操作次数使数组元素相等
3860
【算法千题案例】⚡️每日LeetCode打卡⚡️——58.岛屿的周长
3350
【数据结构和算法】移动零
1270
【算法千题案例】⚡️每日LeetCode打卡⚡️——55.找到所有数组中消失的数字
2710
【小Y学算法】⚡️每日LeetCode打卡⚡️——45.多数元素
3200
相关推荐
【算法千题案例】⚡️每日LeetCode打卡⚡️——59.最大连续 1 的个数
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档