[Leetcode] Missing Number and Missing First Positi

Forest10 發(fā)布于2019-08-14 12:24 / 1797人閱讀

摘要：代碼映射法復(fù)雜度時間空間思路核心思想就是遍歷數(shù)組時，將每個元素，和以該元素為下標的元素進行置換，比如第一個元素是，就將它置換到下標為的地方，而原本下標為的地方的元素就換到第一個來。

Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
For example, Given nums = [0, 1, 3] return 2.
Note: Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

二分搜索法 Binary Search 復(fù)雜度

時間 O(NlogN) 空間 O(1)

思路

先將數(shù)組排序，然后進行二分搜索。顯然，中點的下標和中點的值相同時，說明從起始到中點沒有錯位，缺失數(shù)應(yīng)該在數(shù)組后邊。如果不相等，說明前面已經(jīng)有錯位，缺失數(shù)在左邊。如果缺失數(shù)是最后一個的話，那整個數(shù)組都沒有錯位，則要返回最后一個加1。

注意

雖然原題中這個方法并不是最優(yōu)的，但如果題目中的數(shù)組已經(jīng)排序的了，那二分法就比其他兩個方法要好了。

代碼

public class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        int min = 0, max = nums.length - 1;
        while(min < max){
            int mid = (min + max) / 2;
            // 沒錯位，在右邊。有錯位，則在左邊
            if(mid == nums[mid]){
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }
        // 如果沒有錯位，則返回最后一個數(shù)加1
        return nums[min] == min ? min + 1 : min;
    }
}

等差數(shù)列計算法 Arithmetic Progression 復(fù)雜度

時間 O(N) 空間 O(1)

思路

由題意，大小為n的數(shù)組里的所有數(shù)都是0 - n之間的數(shù)，作為等差數(shù)列，如果沒有缺失的時候它的和是能O(1)計算出來的，所以我們遍歷一遍記錄最大、最小和數(shù)組和，用期望數(shù)組和減去實際數(shù)組和，就是缺失的整數(shù)

注意

缺失0和缺失n的時候要特殊處理，因為他們倆的期望和減去實際和都是0。記錄最小值可以用來判斷是否缺失0。

代碼

public class Solution {
    public int missingNumber(int[] nums) {
        if(nums.length == 0) return 0;
        int max =0, min= nums[0], sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
            max = Math.max(max, nums[i]);
            min = Math.min(min, nums[i]);
        }
        int correctSum = (max + 0) * (max - 0 + 1) / 2;
        return correctSum - sum;
    }
}

異或法 Exclusive OR 復(fù)雜度

時間 O(N) 空間 O(1)

思路

根據(jù)異或的特性，對于一個數(shù)，異或自己是0，異或0是自己，所以我們把0-n都異或一遍，再對著給定數(shù)組異或一遍，結(jié)果就是缺失的數(shù)。

代碼

public class Solution {
    public int missingNumber(int[] nums) {
        int res = 0;
        for(int i = 0; i <= nums.length; i++){
            res ^= i == nums.length ? i : i ^ nums[i];
        }
        return res;
    }
}

First Missing Positive

Given an unsorted integer array, find the first missing positive integer.
For example, Given [1,2,0] return 3, and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.

映射法 復(fù)雜度

時間 O(N) 空間 O(1)

思路

核心思想就是遍歷數(shù)組時，將每個元素，和以該元素為下標的元素進行置換，比如第一個元素是3，就將它置換到下標為3的地方，而原本下標為3的地方的元素就換到第一個來。如果換來的元素也是在正確的位置就檢查下一個元素，否則繼續(xù)交換，直到：

待交換的兩個數(shù)是一樣的

當前位置的元素沒有對應(yīng)的目的地（比如負數(shù)，或者超界元素）

注意

數(shù)組是從0開始的，而正數(shù)是從1開始的，為了簡化映射關(guān)系，把數(shù)組里所有元素都減了1，最后返回答案時再加1即可。

如果最后還沒找到，就說明缺失的是最后一個數(shù)n

代碼

public class Solution {
    public int firstMissingPositive(int[] nums) {
        //減1預(yù)處理數(shù)組，簡化映射關(guān)系
        for(int i = 0; i < nums.length; i++){
            nums[i]--;
        }
        for(int i = 0; i < nums.length;i++){
            while(nums[i]!=i && nums[i] >=0 && nums[i]