leetcode消失的数字

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

题目描述

数组 nums 包含从 0n 的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在 O ( n ) O(n) O(n) 时间内完成吗?

示例 1:

输入:[3,0,1]
输出:2

leetcode链接:消失的数字

⭕️ 思路1:

/*
    思路1:开辟一个 n + 1 的空间,每个元素初始化为-1,遍历目标数组,把目标数组当前元素
        当作新开辟数组的下标并存入当前元素。
            最后遍历新开辟的数组,那个是-1的元素下标就是消失的数字
        [3,0,1]
        [-1 , -1 , -1 , -1]
          0    1    2    3
        [0 , 1 , -1 , 3]
        result : 2
*/
int missingNumber(int* nums, int numsSize){
    int * res = (int *)malloc(sizeof(int) * (numsSize + 1));
    for (int i = 0; i < numsSize + 1; i++) {
        res[i] = -1;
    }
    for (int i = 0; i < numsSize; i++) {
        res[nums[i]] = nums[i];
    }
    for (int i = 0; i < numsSize + 1; i++) {
        if (res[i] == -1) {
            free(res);
            return i;
        }
    }
    free(res);
    return 0;
}

第一种思路时间复杂度 O ( N ) O(N) O(N),空间复杂度 O ( N ) O(N) O(N)

⭕️ 思路2:

/*
    思路2:异或的方式,给一个变量res与目标数组中的所有元素异或,在与0 - numsSize + 1所有元素异或
    因为目标数组中少一个元素,所以最后res的值就保存的是消失的数字。
    [3 , 0 , 1]
    [0 , 1 , 2 , 3]
    3 ^ 3 = 0 -> 0 ^ 0 = 0 -> 1 ^ 1= 0 -> 0 ^ 2 = 2
    result: 2
*/
int missingNumber(int* nums, int numsSize){
    int res = 0;
    for (int i = 0; i < numsSize; i++) {
        res ^= nums[i];
    }
    for (int i = 0; i < numsSize + 1; i++) {
        res ^= i;
    }

    return res;
}

第二种思路时间复杂度 O ( N ) O(N) O(N),空间复杂度 O ( 1 ) O(1) O(1)

⭕️ 思路3:

/*
    思路3:等差数列求和公式 ((首项+尾项)*项数) / 2,用0 - n之间的求和结果减去目标数组的
    每一个元素即可得到消失的数字
*/
int missingNumber(int* nums, int numsSize){
    int resSum = ((0 + numsSize) * (numsSize + 1)) / 2;
    int sum = 0;
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
    }
    return resSum - sum;
}

第三种思路时间复杂度 O ( N ) O(N) O(N),空间复杂度 O ( 1 ) O(1) O(1)

leetcode消失的数字文章来源地址https://www.toymoban.com/news/detail-511070.html

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

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

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

相关文章

  • leetcode刷题:消失的数字

    数组 nums 包含从 0 到 n 的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗? 注意: 本题相对书上原题稍作改动 示例 1: 示例 2: 针对于这道题,我们提供了三种解法: 首先使用快排对数组进行排序,使其变成有序数组,由题意得

    2024年01月24日
    浏览(39)
  • leetcode消失的数字

    数组 nums 包含从 0 到 n 的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在 O ( n ) O(n) O ( n ) 时间内完成吗? 示例 1: 输入:[3,0,1] 输出:2 leetcode链接:消失的数字 ⭕️ 思路1: 第一种思路时间复杂度 O ( N ) O(N) O ( N ) ,空间复杂度 O ( N ) O(N) O ( N ) 。

    2024年02月11日
    浏览(35)
  • 【leetcode】消失的数字

    大家好,我是苏貝,本篇博客带大家刷题,如果你觉得我写的还不错的话,可以给我一个赞👍吗,感谢❤️ 点击查看题目 通过2个for循环,遍历查找0-n中缺少的数字,比较简单,不写,时间复杂度为O(N^2) 点击去了解异或,位置在④.3 异或:两个整数的相同位置:相同为0,不

    2024年01月22日
    浏览(44)
  • 【数据结构刷题】消失的数字和轮转数组

    目录 一.消失的数字  方法一:异或全部元素 方法二:利用等差数列求和-该数组全部元素之和。 二.轮转数组 题型1:实现一个函数,可以左旋字符串中的k个字符。 写法1:暴力求解 根据该题写出右旋转 写法2:三步旋转法(左逆序,右逆序,整体逆序)  根据左旋转写右旋转 题型

    2024年02月16日
    浏览(40)
  • 【快乐手撕LeetCode题解系列】——消失的数字

        😎博客昵称:博客小梦 😊最喜欢的座右铭:全神贯注的上吧!!! 😊作者简介:一名热爱C/C++,算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主! 😘博主小留言:哈喽! 😄各位CSDN的uu们,我是你的博客好友小梦,希望我的文章可以给您带来一定的帮助,话不

    2024年02月01日
    浏览(34)
  • LeetCode:面试题:消失的数字——时间复杂度

    题目:数组nums中包含0~n的所有整数,但其中缺失了一个数,请写代码找出那个缺失的整数,要求在时间复杂度为O(N)的时间内完成 思路1:冒泡排序+遍历(下一个数不等于上一个数+1,这个下一个数就是消失的数) 世间复杂度O(logN*N) 代码: 运行结果: 思路2:0+N利用等

    2024年02月16日
    浏览(40)
  • (C语言版)力扣(LeetCode)面试题 17.04. 消失的数字5种解法

    该题目取自力扣(LeetCode)面试题 17.04. 消失的数字 链接:消失的数字 该题目主要考察时间复杂度的把握,题目如下: 数组nums包含从0到n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗? 注意:本题相对书上原题稍作改动 示例

    2023年04月14日
    浏览(41)
  • LeetCode 1358. 包含所有三种字符的子字符串数目

    滑动窗口的经典题型,直接套模板就行了。

    2024年03月14日
    浏览(60)
  • 快排&超详细,Leetcode排序数组题目带你升华掌握

    大家好,这里是Dark FalmeMater。 这篇文章我将超级仔细地讲解快速排序,快排之所以叫快排,到底有多快,为什么这么快,还有快速排序的优化和改进,通过这篇文章你一定会对快排有进一步的掌握。 快排的历史及介绍 快速排序由C. A. R. Hoare在1962年提出。 它的基本思想是:通

    2024年02月08日
    浏览(53)
  • 【LeetCode题目详解】 977.有序数组的平方 209.长度最小的子数组59.螺旋矩阵II day2

    看完这个题目第一想法就是直接暴力解决,直接将全部平方然后进行排序。比如快排。 代码如下: 时间复杂度是 O(nlogn)或者说【O(n + nlogn)】,括号里面这个是为了比较接下来的方法。 然后看了代码随想录的视频学习了用双指针来写这道题的方法(说实话不看视频真没想到可

    2024年02月13日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包