leetcode 41. First Missing Positive

smallStone 發(fā)布于2019-08-15 10:51 / 2343人閱讀

摘要：題目要求在數(shù)組中找到第一個漏掉的正整數(shù)。思路一暴力排序后尋找排序后尋找顯然是最快的。這些臨時變量可以是排除出的量，也可以是有效量。當遇到的數(shù)字為有效數(shù)字時，則將該數(shù)字放到對應(yīng)當前起始下標其相應(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ù)組中找到第一個漏掉的正整數(shù)。如果可以的話，使用O(N)的時間復(fù)雜度和O(1)的空間復(fù)雜度。

思路一：暴力排序后尋找

排序后尋找顯然是最快的。排序的時間復(fù)雜度要依靠java底層的依賴。之后再用O(N)的時間復(fù)雜度找到第一個漏掉的整數(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ù)雜度

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

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