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

e10101 发布于2019-08-26 10:22 / 2928人阅读

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

题目描述

给定一个包含 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老师的前端补习班」关注我的微信公众号，那么就可以第一时间收到我的最新文章。

GPU云服务器云服务器 LeetCode 服务器偶尔死机 LeetCode_String 服务器会偶尔down掉

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

转载请注明本文地址：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 2019-08-23 15:06 评论0 收藏0
LeetCode偶尔一题 —— 39. Combination Sum（回溯算法系列）

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

linkin 2019-08-23 18:29 评论0 收藏0
LeetCode偶尔一题 —— 64. 最小路径和

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

superw 2019-08-26 10:26 评论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 2019-08-26 14:04 评论0 收藏0
LeetCode偶尔一题 —— 19. 删除链表的倒数第N个节点（链表系列）

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

Anshiii 2019-08-26 10:21 评论0 收藏0