[LeetCode] 41. First Missing Positive

30e8336b8229 發(fā)布于2019-08-16 13:56 / 2092人閱讀

Problem

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3
Example 2:

Input: [3,4,-1,1]
Output: 2
Example 3:

Input: [7,8,9,11,12]
Output: 1
Note:

Your algorithm should run in O(n) time and uses constant extra space.

Solution

class Solution {
    public int firstMissingPositive(int[] A) {
        int i = 0;
        while(i < A.length){
            //we want every A[i] = i+1, so we can find the first missing one
            //if A[i] is negative or out of scope, or it"s in desired position, continue
            if(A[i] == i+1 || A[i] <= 0 || A[i] > A.length) i++;
            //if the number at the desired position of A[i] isn"t A[i], swap them
            else if(A[A[i]-1] != A[i]) swap(A, i, A[i]-1);
            //otherwise, A[A[i]-1] == A[i], we have a duplicate, move on
            else i++;
        }
        
        //now check from the beginning
        i = 0;
        while(i < A.length && A[i] == i+1) i++;
        return i+1;
    }
    
    private void swap(int[] A, int i, int j){
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

GPU云服務(wù)器云服務(wù)器 Positive missing LeetCode 事件 41

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

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/72601.html

相關(guān)文章

leetcode 41. First Missing Positive

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

smallStone 2019-08-15 10:51 評論0 收藏0
LeetCode 之 JavaScript 解答第41題 —— 缺失的第一個正數(shù)（First Mis

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

levius 2019-08-23 16:46 評論0 收藏0
[LintCode] First Missing Positive

摘要：找第一個缺失的正整數(shù)，只要先按順序排列好，也就是，找到第一個和不對應(yīng)的數(shù)就可以了。注意數(shù)組的從開始，而正整數(shù)從開始，所以重寫排列的時候要注意換成，而就是從開始的數(shù)組中的元素。 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

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

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

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