成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

leetcode 41. First Missing Positive

smallStone / 2345人閱讀

摘要：題目要求在數(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,
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.

在數(shù)組中找到第一個(gè)漏掉的正整數(shù)。如果可以的話，使用O(N)的時(shí)間復(fù)雜度和O(1)的空間復(fù)雜度。

思路一：暴力排序后尋找

排序后尋找顯然是最快的。排序的時(shí)間復(fù)雜度要依靠java底層的依賴。之后再用O(N)的時(shí)間復(fù)雜度找到第一個(gè)漏掉的整數(shù)后即退出遍歷。

    public int firstMissingPositive(int[] nums) {
        int size = nums.length;
        if(size == 0) return 1;
        Arrays.sort(nums);
        int positive = 1;
        for(int i = 0 ; ipositive) return positive;
            positive++;
        }
        return positive;
        
    }
思路二：O(1)空間復(fù)雜度

要實(shí)現(xiàn)這種空間復(fù)雜度，一般需要有限數(shù)量的臨時(shí)變量來(lái)記錄遍歷的有效范圍，再利用原有題目中的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)其余的臨時(shí)變量。這些臨時(shí)變量可以是排除出的量，也可以是有效量。在這里我用leftPointer記錄有效數(shù)字的開(kāi)始下標(biāo)（即將無(wú)效數(shù)字轉(zhuǎn)移到leftPointer左側(cè)），利用maxPositive記錄數(shù)組最大有效整數(shù)（換句話說(shuō)，如果一個(gè)數(shù)組的大小為9，則該數(shù)組的最大first missing positive integer即為10，一旦數(shù)組中出現(xiàn)重復(fù)或是小于1或是大于9的數(shù)字，該數(shù)字即為無(wú)效數(shù)字)。當(dāng)遇到的數(shù)字為有效數(shù)字時(shí)，則將該數(shù)字放到對(duì)應(yīng)當(dāng)前起始下標(biāo)leftPointer其相應(yīng)的位置上。

    public int firstMissingPositive2(int[] nums){
        int size = nums.length;
        int positive = 1;
        int leftPointer = 0;
        int maxPositive = size;
        while(leftPointer maxPositive || nums[leftPointer] < positive || nums[leftPointer]==nums[leftPointer+nums[leftPointer]-positive]){
                leftPointer++;
                maxPositive--;
            }else{
                int temp = nums[leftPointer];
                nums[leftPointer] = nums[leftPointer+temp-positive];
                nums[leftPointer+temp-positive] = temp;
            }
        }
        return positive;
    }


想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/67390.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

  • [LintCode] First Missing Positive

    摘要：找第一個(gè)缺失的正整數(shù)，只要先按順序排列好，也就是，找到第一個(gè)和不對(duì)應(yīng)的數(shù)就可以了。注意數(shù)組的從開(kāi)始，而正整數(shù)從開(kāi)始，所以重寫(xiě)排列的時(shí)候要注意換成，而就是從開(kāi)始的數(shù)組中的元素。 Problem Given an unsorted integer array, find the first missing positive integer. Example Given [1,2,0] re...

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

  • [Leetcode] Missing Number and Missing First Positi

    摘要：代碼映射法復(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 t...

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

  • leetcode376. Wiggle Subsequence

    摘要：題目要求扭動(dòng)序列是指數(shù)組中的相鄰兩個(gè)元素的差保證嚴(yán)格的正負(fù)交替，如數(shù)組中相鄰兩個(gè)元素的差為，滿足扭動(dòng)序列的要求?，F(xiàn)在要求從一個(gè)數(shù)組中，找到長(zhǎng)度最長(zhǎng)的扭動(dòng)子序列，并返回其長(zhǎng)度。即前一個(gè)元素和當(dāng)前元素構(gòu)成下降序列，因此代碼如下 題目要求 A sequence of numbers is called a wiggle sequence if the differences between ...

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

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

0條評(píng)論

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