[LeetCode]41.First Missing Positive

【題目】

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.

【分析】

類似於桶排序。

每當A[i] != i+1時,即A[i]不在正確的位置上，需要交換到排序數組中他相應的位置上去。

交換A[i]與A[A[i]-1],直到無法交換。

【代碼】

/*********************************
*   日期：2015-01-13
*   作者：SJF0115
*   題目: 41.First Missing Positive
*   來源：https://oj.leetcode.com/problems/first-missing-positive/
*   結果：AC
*   來源：LeetCode
*   博客：
**********************************/
#include 
using namespace std;

class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        if(A == NULL || n <= 0){
            return 1;
        }//if
        // 交換到在排序數組中應有的位置
        for(int i = 0;i < n;i++){
            // 交換直到不能交換
            while(A[i] != i+1){
                // 是否需要交換
                if(A[i] <= 0 || A[i] > n || A[i] == i+1 || A[i] == A[A[i]-1]){
                    break;
                }//if
                // 交換
                int tmp = A[i];
                A[i] = A[tmp-1];
                A[tmp-1] = tmp;
            }//while
        }//for
        // First Missing Positive
        for(int i = 0;i < n;i++){
            if(A[i] != i+1){
                return i+1;
            }//if
        }//for
        return n+1;
    }
};

int main(){
    Solution solution;
    int A[] = {1,1};
    cout<




【分析二】
<喎?/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+CszixL+1xNfuuvPSu9DQo6zSqsfzTyhuKcq1vMrJz7C1yr7By9PDaGFzaKOstavKx9PWy7XSqmNvbnRhbnQgc3BhY2WjrL7Nw7u3qNTZv6rQwr/VvOTAtL2oaGFzaKGjPGJyPgrV/brD1eK49szixL/W0LSmwO21xMrHMbW9brXEyv2+3aOszOG5qcHL0ru49r2ryuTI67XEyv3X6c2syrHTw9f3aGFzaLHttcS/ycTc0NShozxicj4K09rKx8vjt6i+zcrHo7o8L3A+CjxvbD4KPGxpPgq12tK7senJqMPoxcWz/cv509C3x9X9tcTK/aOsvavL/MPHyejOqtK7uPbO3rnYvfTSqrXE1f3K/ShuJiM0MzsyKaOs0vLOqm4mIzQzOzKyu7/JxNzKx7TwsLg8bGk+CrXatv6x6cmow+ijrL2ryv3X6df3zqpoYXNose3AtMq508OjrNPDyv21xNX9uLrAtLHtyr7Su7j2yv3Kx7fxtObU2tTaQVtd1tChozxicj4KtbHT9rW9QVtpXaOstvhBW2ldyvTT2sf4vORbMSxuXaOsvs2w0UHW0M6709q0y8671sNBW2ldIKhDIDG1xMr91sO3rdeqzqq4usr9oaM8YnI+Csv50tTO0sPHyKHSu7j2QVtpXbXEyrG68qOs0qrIocv8tcRhYnOjrNLyzqrI57n7y/zKx7i6yv21xLuwo6zNqLn9sr3W6NK71q6686Os1ru/ycTcysfO0sPH1ve2r8no1sOzybi6yv21xDxsaT4KtdrI/bHpyajD6KOsyOe5+9P2tb3Su7j2QVtpXcrH1f3K/aOsy7XD92kmIzQzOzHV4rj2yv3Du9PQs/bP1tTaQVtd1tCjrNa70OjSqre1u9i8tL/JoaM8bGk+CsnP0ruyvcO7t7W72KOsy7XD9zG1vW62vNTao6zEx77Nt7W72G4mIzQzOzEKPGg0PqG+tPrC67b+ob88L2g0Pgo8cD48cHJlIGNsYXNzPQ=="brush:java;">class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        if(A == NULL || n <= 0){
            return 1;
        }//if
        int impossValue = n + 2;
        //first run, turn every negetive value into an impossible positive value
        //make every value in A is positive
        for(int i = 0;i < n;i++){
            if(A[i] <= 0){
                A[i] = impossValue;
            }//if
        }//for
        //second run, make A[] as a hash table, A[i] indicate the presence of i + 1
        //the way is that, if k in [1,n] is in A[], then turn A[k -1] to negetive
        for(int i = 0;i < n;i++){
            int value = abs(A[i]);
            if(value <= n){
                A[value-1] = -abs(A[value-1]);
            }//if
        }//for
        //third run, if A[i] is positive, from step 2, we know that i + 1 is missing.
        for(int i = 0;i < n;i++){
            if(A[i] > 0){
                return i+1;
            }//if
        }//for
        //all int from 1 to n is present, then return n + 1
        return n+1;
    }
};