[Leetcode] Missing Number and Missing First Positi

Forest10 發布于2019-08-14 12:24 / 1789人閱讀

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

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 復雜度

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

思路

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

注意

雖然原題中這個方法并不是最優的，但如果題目中的數組已經排序的了，那二分法就比其他兩個方法要好了。

代碼

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;
            }
        }
        // 如果沒有錯位，則返回最后一個數加1
        return nums[min] == min ? min + 1 : min;
    }
}

等差數列計算法 Arithmetic Progression 復雜度

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

思路

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

注意

缺失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 復雜度

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

思路

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

代碼

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.

映射法 復雜度

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

思路

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

待交換的兩個數是一樣的

當前位置的元素沒有對應的目的地（比如負數，或者超界元素）

注意

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

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

代碼

public class Solution {
    public int firstMissingPositive(int[] nums) {
        //減1預處理數組，簡化映射關系
        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]

GPU云服務器云服務器 missing method_missing aapt is missing LeetCode

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64454.html

[LeetCode] 41. First Missing Positive

Problem Given an unsorted integer array, find the smallest missing positive integer. Example 1: Input: [1,2,0]Output: 3Example 2: Input: [3,4,-1,1]Output: 2Example 3: Input: [7,8,9,11,12]Output: 1Note...

30e8336b8229 2019-08-16 13:56 評論0 收藏0
LeetCode 之 JavaScript 解答第41題 —— 缺失的第一個正數（First Mis

摘要：小鹿題目算法思路桶排序思想。再遍歷數組，從下標開始判斷該下標是否存放規定的數據，如果不是則該下標就是這組數據中缺失的最小正整數。桶排序還可以實現在一組數據中查找重復的數據。 Time：2019/4/6Title: First Missing PositiveDifficulty: DifficultyAuthor: 小鹿題目：First Missing Positive Give...

levius 2019-08-23 16:46 評論0 收藏0
leetcode 41. First Missing Positive

摘要：題目要求在數組中找到第一個漏掉的正整數。思路一暴力排序后尋找排序后尋找顯然是最快的。這些臨時變量可以是排除出的量，也可以是有效量。當遇到的數字為有效數字時，則將該數字放到對應當前起始下標其相應的位置上。題目要求 Given an unsorted integer array, find the first missing positive integer. For example,...

smallStone 2019-08-15 10:51 評論0 收藏0
leetcode 268 Missing Number

摘要：題目詳情題目的意思是輸入一個長度為的數組，找到這個數字中不存在于數組中的丟失的數字思路我的想法是，用這個數的和減去數組中的每一個元素的值，最后剩下的值就是丟失的數字解法題目詳情 Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing fr...

tianyu 2019-08-15 13:54 評論0 收藏0
[LintCode/LeetCode] Set Mismatch

Problem The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetit...

Astrian 2019-08-16 12:45 評論0 收藏0