[LintCode] First Missing Positive

snifes 發布于2019-08-14 15:20 / 1542人閱讀

摘要：找第一個缺失的正整數，只要先按順序排列好，也就是，找到第一個和不對應的數就可以了。注意數組的從開始，而正整數從開始，所以重寫排列的時候要注意換成，而就是從開始的數組中的元素。

Problem

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

Example

Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Note

找第一個缺失的正整數，只要先按順序排列好[1, 2, 3, 4, ...]，也就是A[i] = i+1，找到第一個和A[i]不對應的數i+1就可以了。注意數組的index從0開始，而正整數從1開始，所以重寫排列的時候要注意換成index-1，而index就是從A[0]開始的數組A[]中的元素。
我們看一個例子：

[2, 4, -1, 1] --> first for loop --> if (A[i] E (0, A.length) && A[i] != A[A[i]-1]) --> swap(A[i], A[A[i]-1]) --> [4, 2, -1, 1] --> [1, 2, -1, 4] --> second for loop --> A[2] != 3 --> return 2+1 = 3.

之前犯了一個錯誤，因為第二行A[i]的值已經變了，第三行再代入A[A[i]-1]就會出錯：

int temp = A[i];
A[i] = A[A[i]-1];
A[A[i]-1] = temp;

Solution

public class Solution {
    public int firstMissingPositive(int[] A) {
        int len = A.length;
        for (int i = 0; i < len; i++) {
            if (A[i] > 0 && A[i] < len && A[i] != A[A[i]-1]) {
                int temp = A[A[i]-1];
                A[A[i]-1] = A[i];
                A[i] = temp;
                i--; //after the exchange, we need to speculate 
                     //and sort that digit again.
            }
        }
        for (int i = 0; i < len; i++) {
            if (A[i] != i + 1) return i+1; //as array index starts from 0 
                                           //and positive starts from 1.
        }
        return len + 1; //if the array has 1(A[0]) to len(A[len-1])
                        //and missed no one, return the len+1.
    }
}

GPU云服務器云服務器 Positive LintCode missing LintCode134_LRU

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65629.html

leetcode 41. First Missing Positive

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

smallStone 2019-08-15 10:51 評論0 收藏0
[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] Interleaving Positive and Negative Numb

摘要：注意，若正數多于負數，則序列以正數開始，正數結束。所以先統計正數個數，若超過序列長度的一半，則正指針從開始，反之則負指針從開始。注意交換函數的形式，必須是交換指針所指數字的值，而非坐標。 Problem Given an array with positive and negative integers. Re-range it to interleaving with positiv...

calx 2019-08-14 15:22 評論0 收藏0
[LintCode/LeetCode] Super Ugly Number

摘要：建兩個新數組，一個存數，一個存。數組中所有元素初值都是。實現的過程是，一個循環里包含兩個子循環。兩個子循環的作用分別是，遍歷數組與相乘找到最小乘積存入再遍歷一次數組與的乘積，結果與相同的，就將加，即跳過這個結果相同結果只存一次。 Problem Write a program to find the nth super ugly number. Super ugly numbers a...

wuyumin 2019-08-14 15:20 評論0 收藏0