成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

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

e10101 / 2961人閱讀

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

題目描述

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

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

示例 2:

輸入: [9,6,4,2,3,5,7,0,1]  
輸出: 8
最簡單的解法

剛看到的這道題的時(shí)候，第一感覺就是排序，之后直接挨個(gè)比較就能找到缺失的數(shù)字。時(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ù)組來做標(biāo)記。時(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)
};
進(jìn)階

其實(shí)細(xì)心的人可以發(fā)現(xiàn)，數(shù)組是不含重復(fù)數(shù)字的，也就是說我們可以將這道題轉(zhuǎn)化為 等差數(shù)列的前n項(xiàng)和 與 該數(shù)組 的差。時(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)
};

當(dāng)然，這道題也可以用異或來求解，感興趣的朋友可以戳下面的鏈接查看。

原題地址: https://leetcode-cn.com/probl...
代碼不定時(shí)更新，歡迎 star 我的 repo

掃描下方的二維碼或搜索「tony老師的前端補(bǔ)習(xí)班」關(guān)注我的微信公眾號(hào)，那么就可以第一時(shí)間收到我的最新文章。

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/106070.html

相關(guān)文章

  • leetCode算法-268（缺失數(shù)字）

    摘要：給定一個(gè)包含中個(gè)數(shù)的序列，找出中沒有出現(xiàn)在序列中的那個(gè)數(shù)。求合法開始之前我先說一下我的思路個(gè)有序數(shù)字累加和，數(shù)學(xué)里邊是有公式的，我們重溫一下推導(dǎo)過程。 給定一個(gè)包含 0, 1, 2, ..., n 中 n 個(gè)數(shù)的序列，找出 0 .. n 中沒有出現(xiàn)在序列中的那個(gè)數(shù)。 示例 1: 輸入: [3,0,1]輸出: 2示例 2: 輸入: [9,6,4,2,3,5,7,0,1]輸出: 8 下面我...

    geekzhou 評(píng)論0 收藏0

  • LeetCode偶爾一題 —— 39. Combination Sum（回溯算法系列）

    摘要：輸入輸出分析題目由于我們需要找到多個(gè)組合，簡單的使用循環(huán)肯定是不行的，這時(shí)候我們可以使用回溯算法來解決這個(gè)問題。用回溯算法解決問題的一般步驟針對(duì)所給問題，定義問題的解空間，它至少包含問題的一個(gè)最優(yōu)解。 題目描述 Given a set of candidate numbers (candidates) (without duplicates) and a target number ...

    linkin 評(píng)論0 收藏0

  • LeetCode偶爾一題 —— 64. 最小路徑和

    摘要：題目描述給定一個(gè)包含非負(fù)整數(shù)的網(wǎng)格，請(qǐng)找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小。示例輸入輸出解釋因?yàn)槁窂降目偤妥钚　８鶕?jù)題中描述，我們知道每次只能向下或者向右移動(dòng)一步，我們以此為依據(jù)畫出示例中所有可能的路徑 題目描述 給定一個(gè)包含非負(fù)整數(shù)的 m x n 網(wǎng)格，請(qǐng)找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小。 說明：每次只能向下或者向右移動(dòng)一步。示例: ...

    superw 評(píng)論0 收藏0

  • LeetCode偶爾一題 —— 832. 翻轉(zhuǎn)圖像

    題目描述 showImg(https://user-gold-cdn.xitu.io/2019/8/19/16caa79a911512b4?w=761&h=578&f=png&s=55670); 分析題目 按照題意我們只要先對(duì)每個(gè)子數(shù)組先做逆序，再做 0 --> 1 和 1 --> 0 的替換即可，于是我們可以寫出以下代碼： /** * @param {number[][]} A * @ret...

    WalkerXu 評(píng)論0 收藏0

  • LeetCode偶爾一題 —— 19. 刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)（鏈表系列）

    摘要：題目描述給定一個(gè)鏈表，刪除鏈表的倒數(shù)第個(gè)節(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。示例給定一個(gè)鏈表和當(dāng)刪除了倒數(shù)第二個(gè)節(jié)點(diǎn)后，鏈表變?yōu)楹唵蔚乃悸酚靡粋€(gè)數(shù)組保存所有的鏈表節(jié)點(diǎn)，遍歷完之后可以知道倒數(shù)第個(gè)鏈表節(jié)點(diǎn)。 題目描述 給定一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。示例： 給定一個(gè)鏈表: 1->2->3->4->5, 和 n = 2. 當(dāng)刪除了倒數(shù)第二個(gè)節(jié)點(diǎn)后，鏈表變?yōu)?1-...

    Anshiii 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<