资讯专栏INFORMATION COLUMN

LeetCode偶尔一题 —— 268. 缺失数字

e10101 / 2904人阅读

摘要:题目描述给定一个包含中个数的序列,找出中没有出现在序列中的那个数。示例输入输出示例输入输出最简单的解法刚看到的这道题的时候,第一感觉就是排序,之后直接挨个比较就能找到缺失的数字。

题目描述

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。
示例 1:

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

示例 2:

输入: [9,6,4,2,3,5,7,0,1]  
输出: 8
最简单的解法

刚看到的这道题的时候,第一感觉就是排序,之后直接挨个比较就能找到缺失的数字。时间复杂度O(nlog(n))空间复杂度O(1)

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    let i = 0
    nums.sort((a, b) => a - b)
    for (i = 0; i < nums.length; i++) {
        if (i !== nums[i]) {
            return i
        }
    }
    return i
};

写完之后感觉不用排序也行,可以开辟新的数组来做标记。时间复杂度O(n)空间复杂度O(n)

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    let i = 0, tmp = []
    for (i = 0; i < nums.length + 1; i++) {
        tmp[i] = true
    }
    for (i = 0; i < nums.length; i++) {
        if (tmp[nums[i]]) {
            tmp[nums[i]] = false
        }
    }
    return tmp.indexOf(true)
};
进阶

其实细心的人可以发现,数组是不含重复数字的,也就是说我们可以将这道题转化为 等差数列的前n项和该数组 的差。时间复杂度O(n), 空间复杂度O(1)

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    let n = nums.length, sum = (1 + n) * n / 2
    return sum - nums.reduce((cur, next) => cur + next)
};

当然,这道题也可以用异或来求解,感兴趣的朋友可以戳下面的链接查看。

原题地址: https://leetcode-cn.com/probl...
代码不定时更新,欢迎 star 我的 repo

扫描下方的二维码或搜索「tony老师的前端补习班」关注我的微信公众号,那么就可以第一时间收到我的最新文章。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/106070.html

相关文章

  • leetCode算法-268缺失数字

    摘要:给定一个包含中个数的序列,找出中没有出现在序列中的那个数。求合法开始之前我先说一下我的思路个有序数字累加和,数学里边是有公式的,我们重温一下推导过程。 给定一个包含 0, 1, 2, ..., n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。 示例 1: 输入: [3,0,1]输出: 2示例 2: 输入: [9,6,4,2,3,5,7,0,1]输出: 8 下面我...

    geekzhou 评论0 收藏0
  • LeetCode偶尔一题 —— 39. Combination Sum(回溯算法系列)

    摘要:输入输出分析题目由于我们需要找到多个组合,简单的使用循环肯定是不行的,这时候我们可以使用回溯算法来解决这个问题。用回溯算法解决问题的一般步骤针对所给问题,定义问题的解空间,它至少包含问题的一个最优解。 题目描述 Given a set of candidate numbers (candidates) (without duplicates) and a target number ...

    linkin 评论0 收藏0
  • LeetCode偶尔一题 —— 64. 最小路径和

    摘要:题目描述给定一个包含非负整数的网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。示例输入输出解释因为路径的总和最小。根据题中描述,我们知道每次只能向下或者向右移动一步,我们以此为依据画出示例中所有可能的路径 题目描述 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。示例: ...

    superw 评论0 收藏0
  • LeetCode偶尔一题 —— 832. 翻转图像

    题目描述 showImg(https://user-gold-cdn.xitu.io/2019/8/19/16caa79a911512b4?w=761&h=578&f=png&s=55670); 分析题目 按照题意我们只要先对每个子数组先做逆序,再做 0 --> 1 和 1 --> 0 的替换即可,于是我们可以写出以下代码: /** * @param {number[][]} A * @ret...

    WalkerXu 评论0 收藏0
  • LeetCode偶尔一题 —— 19. 删除链表的倒数第N个节点(链表系列)

    摘要:题目描述给定一个链表,删除链表的倒数第个节点,并且返回链表的头结点。示例给定一个链表和当删除了倒数第二个节点后,链表变为简单的思路用一个数组保存所有的链表节点,遍历完之后可以知道倒数第个链表节点。 题目描述 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1-...

    Anshiii 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<