[LeetCode-バケツソート]41.First Missing Positive

1問題
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.
2分析
テーマは1つの無秩序な整数の配列をあげて、求めます:この配列の中でしかも最小の整数ではありませんて、そして時間の複雑さと空間の複雑さに対して要求しました.この問題を解く直感はソートであり,与えられたデータをソートできれば,この配列にない最小整数を容易に見つけることができる.しかし,問題は時間複雑度O(n)を要求するが,「比較モデル」を用いたソートアルゴリズムは望ましくなく,線形時間ソートアルゴリズムしか用いられない.観察結果:

配列にない最小正の整数は配列中の正の整数の影響のみを受け、配列中の負の数と0がどのように分布しても、求められた結果には影響しません.したがって、配列内の正の整数をソートするだけです.

正の整数のソート中に、配列に重複数が存在する場合、いくら繰り返しても現れない最小正の整数には影響しません.したがって、ソート中に重複は無視できます.

配列にない最小正整数の最小値は1であり、最大値はn+1である.

以上の2点観察に基づいて,線形時間ソートアルゴリズムにおけるバケツソートを用いることができる.問題は空間複雑度が定数であることを要求するため,入力配列上でのみ操作でき,新しい空間を割り当てることができない.配列長をnとすると,配列全体のn個の位置をn個のバケツと見なし,各バケツはそれぞれ正の整数1,2,3,...,n .配列全体を巡って、次の操作を行います(iは現在アクセス中の配列を下付きで表し、a[i]は現在アクセス中の配列値を表します).

a[i] < 0の場合、この位置はスキップされ、i = i + 1が実行される.

a[i] > nの場合、i = i + 1が実行される.

は、a[i]を対応するバケツの値a[a[i]と比較し、両者が等しい場合はi = i + 1を実行する.

以上の点が満たされない場合、a[i]は対応するバケツの値a[a[i]]と交換される.交換後、上記の手順を繰り返します.交換に成功した後も、下のiにアクセスします.

並べ替えが完了した後、再び配列を巡り、最初の配列値が下付きと等しくない位置が求められる数字です.配列全体の値がそれぞれの下付き文字と等しい場合、求められる数字はn+1である.
3コード

public class Solution {
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        int i = 0;
        while(i < len){
            if(nums[i] <= len && nums[i] >= 1 && nums[i] != nums[nums[i]-1]){
                int temp = nums[nums[i]-1];
                nums[nums[i]-1] = nums[i];
                nums[i] = temp;
            }else{
                i++;
            }
        }

        for(int id = 0; id < len; id++){
            if(nums[id] != id+1){
                return id+1;
            }
        }
        return len+1;
    }
}