LeetCode偶爾一題 —— 268. 缺失數字

e10101 發布于2019-08-26 10:22 / 2957人閱讀

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

題目描述

給定一個包含 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掉

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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