LeetCode偶爾一題 —— 268. 缺失數(shù)字

e10101 發(fā)布于2019-08-26 10:22 / 2951人閱讀

摘要：題目描述給定一個包含中個數(shù)的序列，找出中沒有出現(xiàn)在序列中的那個數(shù)。示例輸入輸出示例輸入輸出最簡單的解法剛看到的這道題的時候，第一感覺就是排序，之后直接挨個比較就能找到缺失的數(shù)字。

題目描述

給定一個包含 0, 1, 2, ..., n 中 n 個數(shù)的序列，找出 0 .. n 中沒有出現(xiàn)在序列中的那個數(shù)。
示例 1:

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

示例 2:

輸入: [9,6,4,2,3,5,7,0,1]  
輸出: 8

最簡單的解法

剛看到的這道題的時候，第一感覺就是排序，之后直接挨個比較就能找到缺失的數(shù)字。時間復(fù)雜度：O(nlog(n))，空間復(fù)雜度：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
};

寫完之后感覺不用排序也行，可以開辟新的數(shù)組來做標記。時間復(fù)雜度：O(n)，空間復(fù)雜度：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)
};

進階

其實細心的人可以發(fā)現(xiàn)，數(shù)組是不含重復(fù)數(shù)字的，也就是說我們可以將這道題轉(zhuǎn)化為 等差數(shù)列的前n項和 與 該數(shù)組 的差。時間復(fù)雜度：O(n), 空間復(fù)雜度：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老師的前端補習(xí)班」關(guān)注我的微信公眾號，那么就可以第一時間收到我的最新文章。