亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

[Leetcode] Missing Number and Missing First Positi

Forest10 / 1838人閱讀

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

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ù)雜度

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

思路

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

注意

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

代碼 
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;
            // 沒(méi)錯(cuò)位，在右邊。有錯(cuò)位，則在左邊
            if(mid == nums[mid]){
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }
        // 如果沒(méi)有錯(cuò)位，則返回最后一個(gè)數(shù)加1
        return nums[min] == min ? min + 1 : min;
    }
}
等差數(shù)列計(jì)算法 Arithmetic Progression 復(fù)雜度

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

思路

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

注意

缺失0和缺失n的時(shí)候要特殊處理，因?yàn)樗麄儌z的期望和減去實(shí)際和都是0。記錄最小值可以用來(lái)判斷是否缺失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ù)雜度

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

思路

根據(jù)異或的特性，對(duì)于一個(gè)數(shù)，異或自己是0，異或0是自己，所以我們把0-n都異或一遍，再對(duì)著給定數(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ù)雜度

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

思路

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

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

當(dāng)前位置的元素沒(méi)有對(duì)應(yīng)的目的地（比如負(fù)數(shù)，或者超界元素）

注意

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

如果最后還沒(méi)找到，就說(shuō)明缺失的是最后一個(gè)數(shù)n

代碼 
public class Solution {
    public int firstMissingPositive(int[] nums) {
        //減1預(yù)處理數(shù)組，簡(jiǎn)化映射關(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]

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/64454.html

相關(guān)文章

  • [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 評(píng)論0 收藏0

  • LeetCode 之 JavaScript 解答第41題 —— 缺失的第一個(gè)正數(shù)（First Mis

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

    levius 評(píng)論0 收藏0

  • leetcode 41. First Missing Positive

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

    smallStone 評(píng)論0 收藏0

  • leetcode 268 Missing Number

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

    tianyu 評(píng)論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 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<