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

最简单的解法

刚看到的这道题的时候，第一感觉就是排序，之后直接挨个比较就能找到缺失的数字。时间复杂度：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/problems/missing-number/
代码不定时更新，欢迎 star 我的 repo

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