力扣--268丢失的数字(三种解法)

这篇具有很好参考价值的文章主要介绍了力扣--268丢失的数字(三种解法)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档


给定一个包含 [0, n] 中 n 个数的数组 nums ,找出 [0, n] 这个范围内没有出现在数组中的那个数。 示例 1:

输入:nums = [3,0,1] 输出:2 解释:n = 3,因为有 3 个数字,所以所有的数字都在范围 [0,3] 内。2
是丢失的数字,因为它没有出现在 nums 中。
示例 2:

输入:nums = [0,1] 输出:2 解释:n = 2,因为有 2 个数字,所以所有的数字都在范围 [0,2] 内。2
是丢失的数字,因为它没有出现在 nums 中。
示例 3:

输入:nums = [9,6,4,2,3,5,7,0,1] 输出:8 解释:n = 9,因为有 9 个数字,所以所有的数字都在范围
[0,9] 内。8 是丢失的数字,因为它没有出现在 nums 中。
示例 4:

输入:nums = [0] 输出:1 解释:n = 1,因为有 1 个数字,所以所有的数字都在范围 [0,1] 内。1
是丢失的数字,因为它没有出现在 nums 中。

题目已经清楚的说明了,要我们找到[ 0 n]中数组每出现的数字

解法1

大家看到题的时候的第一想法就是循环嵌套吧,通过遍历来找到那个数字。
好,那么我们就来实现一下

int missingNumber(int* nums, int numsSize) {
	for (int i = 0; i <= numsSize; i++) {//第一个循环,将[1~n]的数字遍历一次
		int t=0;//标志变量
		for (int j =0 ; j < numsSize; j++) {//在数组中寻找i找不到就是的话就是丢失的数字
			if (nums[j] == i)
			{
				t = 1;//找到i就是t=1加打破
				break;
			}
		}
		if (t == 0)
			return i;//返回丢失的数字
	}

}

优点:这种解法简单,只需要循环嵌套即可
缺点:时间复杂度O(n*n),时间过长可能超过时限

解法2

我们要注意一个点就是这些数字是[ 0 n]且数组数字不重复,那么我们可以将0~n都加起来然后再减去数组中的所有数字,得到的就是丢失的数字了
实现:

int missingNumber(int* nums, int numsSize) {
    int r=0;
    for(int i=1;i<=numsSize;i++)//将0-n的数字都加起来
          r=r+i;     
    for(int i=0;i<numsSize;i++)
    r=r-nums[i];减去数组中所有的数字
    return r;
}

这种解法很好,时间复杂度在O(n),也很容易实现

解法3

第三种方法就是利用异或了

异或有两个性质
1.0和任何一个数异或都等于那个数
2.相同的数字异或的结果为0

我们可以设置一个数为0,再和[0-n]的数字异或,之后再和数组的各个元素异或,这样一来相同的数字就被抵消了,剩下0和丢失的那个数,又因为0和任何一个数异或都等于那个数,所以最后得到的数就是丢失的数字了
实现:

int missingNumber(int* nums, int numsSize) {
    int r = 0;
    for (int i = 1; i <= numsSize; i++)//让r和0-n的数字都异或
        r = r ^ i;
    for (int i = 0; i < numsSize; i++)//再和数组中的所有元素异或,最终就是丢失的数字了
        r = r ^ nums[i];
    return r;

这种解法很好,就是有点难想到,时间复杂度为O(n)

总结

相比于第一种后面的两种在时间上有优势,但是后面两种有点难想到,特别是第三种

今天的分享就到这里了,谢谢大家的观看文章来源地址https://www.toymoban.com/news/detail-758843.html

到了这里,关于力扣--268丢失的数字(三种解法)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【leetcode 力扣刷题】移除链表元素 多种解法

    题目链接:203.移除链表元素 题目内容: 理解题意:就是单纯的删除链表中所有值等于给定的val的节点。上一篇博客中介绍了链表的基础操作,在删除链表中节点时,需要注意的是头节点: 如果没有虚拟头节点,那么对头节点的删除需要做不同的处理,head = head-next; 如果有

    2024年02月12日
    浏览(47)
  • 2235.两整数相加:19种语言解法(力扣全解法)

    力扣题目链接:https://leetcode.cn/problems/add-two-integers/ 给你两个整数  num1 和 num2 ,返回这两个整数的和。   示例 1: 示例 2:   提示: -100 = num1, num2 = 100 时间复杂度 O ( 1 ) O(1) O ( 1 ) 空间复杂度 O ( 1 ) O(1) O ( 1 ) AC代码 C++ C Python Python2 Java C# Javascript Ruby Swift Go Scala Kotlin Rust PHP

    2024年02月12日
    浏览(36)
  • ​LeetCode解法汇总2544. 交替数字和

    https://github.com/September26/java-algorithms 给你一个正整数  n  。 n  中的每一位数字都会按下述规则分配一个符号: 最高有效位  上的数字分配到  正  号。 剩余每位上数字的符号都与其相邻数字相反。 返回所有数字及其对应符号的和。 示例 1: 示例 2: 示例 3: 提示: 1 = n

    2024年02月16日
    浏览(34)
  • C语言题目的多种解法分享 2之字符串左旋和补充题

    有的时候,这个系列专栏中的解法之间并无优劣,只是给大家提供不同的解题思路 我决定将代码实现的过程写成注释,方便大家直接找到对应的函数,只有需要补充说明的知识才会单拿出来强调 这个系列的文章会更的比较慢,因为多种解法的需要慢慢收集、整理 实现一个函

    2024年02月13日
    浏览(55)
  • 【leetcode 力扣刷题】回文串相关题目(KMP、动态规划)

    题目链接:5. 最长回文子串 题目内容: 题目就是要我们找s中的回文子串,还要是最长的。其实想想,暴力求解也行……就是遍历所有的子串,同时判断是不是回文串,是的话再和记录的最大长度maxlen比较,如果更长就更新。时间复杂度直接变成O(n^3)。 优化的点在于,假设子

    2024年02月09日
    浏览(45)
  • C语言-杨辉三角的三种解法-简单易懂篇

    这里我们先实现第二张图的这种杨辉三角,在第二张图的基础上加上对数字前面空格的控制就好了,这个不难实现,重点是先把杨辉三角成功的打印出来。 这里我们先给出第一种方法: 我们可以创建一个二维的数组,数组的第一行的元素和对角线的元素,全部位1,然后从第

    2024年02月04日
    浏览(41)
  • Java LeetCode篇-深入了解二叉树经典解法(三种方式实现:获取二叉树的最大深度)

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍    文章目录         1.0 对称二叉树         1.1 判断对称二叉树实现思路         1.2 代码实现:判断对称二叉树         2.0 二叉树的最大深度         2.1 使用递归实现获取二叉树的最大深度思

    2024年02月05日
    浏览(76)
  • 消失的数字(c语言多种解法)

    该题目取自力扣(LeetCode)面试题 17.04. 消失的数字 该题目主要考察时间复杂度的把握,题目如下: 数组nums包含从0到n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗? 示例 1: 输入:[3,0,1] 输出:2 示例 2: 输入:[9,6,4,2,3,5,7,

    2024年02月21日
    浏览(35)
  • Leetcode 268. Missing Number

    Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array. Sum all the numbers as x x x and use n ( n + 1 ) 2 − x frac{n(n+1)}{2} - x 2 n ( n + 1 ) ​ − x .

    2024年02月14日
    浏览(40)
  • 力扣(LeetCode)算法_C++—— 只出现一次的数字

    给你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。 示例 1 : 输入:nums = [2,2,1] 输出:1 示例 2 : 输入:nums = [4,

    2024年02月09日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包