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

geekzhou 發(fā)布于2019-08-23 15:06 / 1370人閱讀

摘要：給定一個(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

下面我用兩種方法，一塊了解一下。

求合法

         // 開始之前我先說一下我的思路
        //0-n個(gè)有序數(shù)字累加和，數(shù)學(xué)里邊是有公式的，我們重溫一下推導(dǎo)過程。
        // 0, 1          n為1 個(gè)數(shù)為2， 累加和為1
        // 0, 1, 2       n為2 個(gè)數(shù)為3，累加和為3
        // 0, 1, 2, 3    n為3 個(gè)數(shù)為4，累加和為6
        // 0, 1, 2, 3 ,4 n為4 個(gè)數(shù)為5， 累加和為10

        // 思考一下，n已知所以我們從n上找規(guī)律

        //以上我們推出 (n*個(gè)數(shù))/2 = 累加和,是不是這個(gè)理？

        // n知道 累加和知道，少那個(gè)我們不就知道了嗎？

        // 完整的n序列和-缺失數(shù)字的累加和=缺失數(shù)字

        // 翻譯成代碼
        var arr = [0, 1, 3]

        function findNum(nums) {
            let len = nums.length
            let n = len * (len + 1) / 2
            let n1 = nums.reduce((num, item) => {
                return num + item
            }, 0)
            console.log(n, n1)
            return n - n1
        };

        console.log(findNum(arr))//2

索引查找法

//先解析思路,0-n序列，數(shù)組的索引和0-n序列正好能一一對(duì)應(yīng)，不過因?yàn)橛锌赡苁莵y序，所以不能直接挨個(gè)匹配索引對(duì)比，我們需要換個(gè)思路。
//因?yàn)槭切蛄校m然亂序，只是和遍歷n的索引值缺一個(gè)，這就簡(jiǎn)單了，我們通過遍歷n來查找對(duì)應(yīng)的剩余數(shù)組，找不到的就是我們要找的缺失數(shù)字，怎么找對(duì)應(yīng)數(shù)字呢？你猜對(duì)了我們用indexOf()
          function findNum1(nums) {
            let len = nums.length + 1
            for (let i = 0; i < len; i++) {
                if (nums.indexOf(i) === -1) {
                    return i
                }
            }
        };
        findNum1(arr)

完美，只不過沒有第一種的效率高！畢竟每一次indexOf也是一次遍歷過程。