leetcode 41. First Missing Positive

smallStone 發布于2019-08-15 10:51 / 2337人閱讀

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

題目要求

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)的空間復雜度。

思路一：暴力排序后尋找

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

    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)空間復雜度

要實現這種空間復雜度，一般需要有限數量的臨時變量來記錄遍歷的有效范圍，再利用原有題目中的數據結構來存儲其余的臨時變量。這些臨時變量可以是排除出的量，也可以是有效量。在這里我用leftPointer記錄有效數字的開始下標（即將無效數字轉移到leftPointer左側），利用maxPositive記錄數組最大有效整數（換句話說，如果一個數組的大小為9，則該數組的最大first missing positive integer即為10，一旦數組中出現重復或是小于1或是大于9的數字，該數字即為無效數字)。當遇到的數字為有效數字時，則將該數字放到對應當前起始下標leftPointer其相應的位置上。

    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;
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

GPU云服務器云服務器 Positive missing 事件 41 Leetcod

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/67390.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
[LintCode] First Missing Positive

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

snifes 2019-08-14 15:20 評論0 收藏0
[Leetcode] Missing Number and Missing First Positi

摘要：代碼映射法復雜度時間空間思路核心思想就是遍歷數組時，將每個元素，和以該元素為下標的元素進行置換，比如第一個元素是，就將它置換到下標為的地方，而原本下標為的地方的元素就換到第一個來。 Missing Number Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one t...

Forest10 2019-08-14 12:24 評論0 收藏0
leetcode376. Wiggle Subsequence

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

CoffeX 2019-08-16 17:10 評論0 收藏0