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

01 看題和準備

今天介紹的是LeetCode算法題中Easy級別的第99題（順位題號是448）。給定一個整數(shù)數(shù)組，其中1≤a[i]≤n（n =數(shù)組的大?。恍┰爻霈F(xiàn)兩次，其他元素出現(xiàn)一次。找到[1，n]包含的所有元素，這些元素不會出現(xiàn)在此數(shù)組中。你可以在沒有額外空間和O（n）運行時的情況下完成嗎？ 您可以假設返回的列表不計入額外空間。例如：

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

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

02 第一種解法

特殊情況：當數(shù)組中沒有元素時，直接返回空list。

正常情況：先將數(shù)組排序，然后獲取數(shù)組的第一個元素作為起始索引index，如果數(shù)組第一個元素不等于1，因為1≤a[i]≤n，所以需要先將前面缺的部分補起來。然后開始循環(huán)判斷數(shù)組中的元素，如果index和當前元素相等，那么index自加1，循環(huán)內(nèi)部的指針也加1；反之不相等，則需要判斷當前元素和前一個元素是否相等，如果相等，循環(huán)內(nèi)部的指針加1，否則就將index添加進list中，index再自加1。最后，還需要在判斷一次，如果index小于數(shù)組的長度，則需要將后面缺的數(shù)也補起來。

此解法的時間復雜度是O(n log(n))，空間復雜度是O(1)。

public List<Integer> findDisappearedNumbers(int[] nums) {
    List<Integer> list = new ArrayList<Integer>();
    if (nums == null || nums.length < 1) {
        return list;
    }
    Arrays.sort(nums);
    int index = nums[0];
    if (index != 1) {
        for (int k=1; k<index; k++) {
            list.add(k);
        }
    }
    for (int i=0; i<nums.length; ) {
        if (index == nums[i]) {
            index++;
            i++;
        } else {
            if (nums[i] == nums[i-1]) {
                i++;
            } else {
                list.add(index++);
            }
        }
    }
    for (int j = index; j<=nums.length; j++) {
        list.add(j);
    }
    return list;
}

03 第二種解法

利用標記。因為1≤a[i]≤n，我們可以單獨再新建一個數(shù)組，數(shù)組的長度是n+1，然后將nums中的元素作為索引，在新數(shù)組中對元素進行自加。然后判斷新數(shù)組中，那些等于0的元素的索引就是nums中缺失的數(shù)。

public List<Integer> findDisappearedNumbers2(int[] nums) {
    List<Integer> list = new ArrayList<Integer>();
    if (nums == null || nums.length < 1) {
        return list;
    }
    int[] temp = new int[nums.length+1];
    for (int num : nums) {
        temp[num]++;
    }
    for (int i=1; i<temp.length; i++) {
        if (temp[i] == 0) {
            list.add(i);
        }
    }
    return list;
}

04 第三種解法

還是利用標記。在第二種解法中，我們使用了新數(shù)組，在此解法中，我們直接對nums進行標記。先遍歷nums的元素，順著索引，將其中的正數(shù)元素標記為負數(shù)。然后再去遍歷數(shù)組，如果當前元素為正數(shù)，則說明其所在索引沒有遇見過，就將其添加進list中。

public List<Integer> findDisappearedNumbers3(int[] nums) {
    List<Integer> list = new ArrayList<Integer>();
    if (nums == null || nums.length < 1) {
        return list;
    }
    for (int i = 0; i < nums.length; i++) {
        int val = Math.abs(nums[i]) - 1;
        if (nums[val] > 0) {
            nums[val] = -nums[val];
        }
    }
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            list.add(i+1);
        }
    }
    return list;
}

05 小結(jié)

算法專題目前已日更超過三個月，算法題文章99+篇，公眾號對話框回復【數(shù)據(jù)結(jié)構(gòu)與算法】、【算法】、【數(shù)據(jù)結(jié)構(gòu)】中的任一關鍵詞，獲取系列文章合集。

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