這是悅樂書的第200次更新，第209篇原創(chuàng)

01 看題和準(zhǔn)備

今天介紹的是LeetCode算法題中Easy級(jí)別的第65題（順位題號(hào)是268）。給定一個(gè)包含n個(gè)不同數(shù)字的數(shù)組，取自0,1,2，...，n，找到數(shù)組中缺少的數(shù)字。例如：

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

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

注意：您的算法應(yīng)該以線性運(yùn)行時(shí)復(fù)雜性運(yùn)行。 你能用恒定的額外空間復(fù)雜度來實(shí)現(xiàn)嗎？

本次解題使用的開發(fā)工具是eclipse，jdk使用的版本是1.8，環(huán)境是win7 64位系統(tǒng)，使用Java語言編寫和測(cè)試。

02 第一種解法

特殊情況：當(dāng)nums為null的時(shí)候，或者nums中沒有元素的時(shí)候，直接返回0即可。

正常情況：缺失的數(shù)字分為三種情況：一是缺失的數(shù)字在中間，比如{0,1,2,4}，此時(shí)缺失的數(shù)字是3；二是缺失的數(shù)字在末尾，比如{0,1,2,3}，此時(shí)缺失的數(shù)字就是4；三是缺失的數(shù)字在頭部，比如{1,2,3,4}，此時(shí)缺失的數(shù)字就是0。

先將數(shù)組從小到大排序，然后使用for循環(huán)，判斷索引是否相等，不相等就是中間缺失的那個(gè)數(shù)，如果中間不缺數(shù)，最后返回索引即可，因?yàn)橐呀?jīng)在循環(huán)體中自加1，最后返回的時(shí)候不用再加1。

此解法時(shí)間復(fù)雜度是O(nlog(n))，空間復(fù)雜度是O(1)。

public int missingNumber(int[] nums) {
    if (nums == null || nums.length < 1) {
        return 0;
    }
    Arrays.sort(nums);
    int index;
    for (index = 0; index < nums.length; index++) {
        if (index != nums[index]) {
            return index;
        }
    }
    return index;
}

03 第二種解法

通過觀察，我們可以發(fā)現(xiàn)，nums中的元素組成是一個(gè)以1為等差的等差數(shù)列，我們可以通過等差數(shù)列的和來找出缺失的元素，其求和公式為：

Sum = n*(A1+An)/2

題目中的數(shù)組是從0開始到n，即A1=0，An=n-1，我們計(jì)算的時(shí)候可以從1到數(shù)組長(zhǎng)度，即A1=1，An=n，然后對(duì)其求和，借助for循環(huán)，此處有兩種方式，一是用和去減每一個(gè)元素，最后剩下的就是缺失的元素；二是算出數(shù)組所有元素的和，再算等差數(shù)列的和與其的差值，就是缺失的元素。

此解法的時(shí)間復(fù)雜度是O(n)，空間復(fù)雜度是O(1)。

public int missingNumber2(int[] nums) {
    if (nums == null || nums.length < 1) {
        return 0;
    }
    int sum = (nums.length*(1+nums.length))/2;
    for (int n : nums) {
        sum -= n;
    }
    return sum;
}

04 第三種解法

借助位運(yùn)算中的異或（^）運(yùn)算，通過一個(gè)運(yùn)算公式：a^b^b = a，我們可以算出缺失的那個(gè)數(shù)字。例如：

數(shù)組nums={0,1,2,4}，數(shù)組的索引是{0,1,2,3}

missing=4^(0^0)^(1^1)^(2^2)^(4^3)

       =3^(0^0)^(1^1)^(2^2)^(4^4)

       =3

其中最開始的4就是數(shù)組的長(zhǎng)度。

此解法的時(shí)間復(fù)雜度是O(n)，空間復(fù)雜度是O(1)。

public int missingNumber3(int[] nums) {
    if (nums == null || nums.length < 1) {
        return 0;
    }
    int xor = nums.length;
    for (int i = 0; i < nums.length; i ++) {
        xor = xor ^ nums[i] ^ i;
    }
    return xor;
}

05 第四種解法

使用HashSet，先將數(shù)組中的每一個(gè)元素存入其中，然后利用for循環(huán)，從0到n，判斷set中是否包含當(dāng)前索引，不包含的就是缺失的那個(gè)數(shù)。

此解法也可以用HashMap做，思路都是一樣的，時(shí)間復(fù)雜度是O(n)，空間復(fù)雜度是O(n)。

public int missingNumber4(int[] nums) {
    if (nums == null || nums.length < 1) {
        return 0;
    }
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        set.add(num);
    }
    for (int i=0; i<=nums.length; i++) {
        if (!set.contains(i)) {
            return i;
        }
    }
    return -1;
}

06 小結(jié)

算法專題目前已連續(xù)日更超過一個(gè)月，算法題文章65+篇，公眾號(hào)對(duì)話框回復(fù)【數(shù)據(jù)結(jié)構(gòu)與算法】、【算法】、【數(shù)據(jù)結(jié)構(gòu)】中的任一關(guān)鍵詞，獲取系列文章合集。

以上就是全部?jī)?nèi)容，如果大家有什么好的解法思路、建議或者其他問題，可以下方留言交流，點(diǎn)贊、留言、轉(zhuǎn)發(fā)就是對(duì)我最大的回報(bào)和支持！