LeetCode 解答 #41. First Missing Positive プログラミング練習

問題：

難易度:　hard
入力:　int 型array[]
目的: 欠けた一番小さい正数を求めよ
出力:　int

入力の中に含まれていない一番小さい正数を探す問題です。
例えば入力が[3,4,-1,1]であった場合、
欠けた一番小さい正数は2です。
マイナス部分と0は無視してかまいません。
一見簡単な問題に見えますが、
時間をO(n), メモリーをO(1)に抑えなければならないのでソートが出来ません。
この制限により難易度が一気に上がります。

注意すべき事:　

• 入力はソートされていない

• 時間をO(n), メモリーをO(1)に抑えなければならない

以下回答です。

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i=0; i<n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums, i, nums[i] - 1);
            }
        }

        for (int i=0; i<n; i++) {
            if (nums[i] != i + 1) return i+1;
        }
        return n+1;
    }
    
    public void swap (int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

ソートをするとO(n)を超えてしまいますので使えません。
全体のソートはできませんが、
部分的なソートなら出来ます。
つまりこの問題は、正数iをnums[i-1]にソートすればいいのです。
例えば5であればnums[4]に並び替え、2であればnums[1]に並べます。
すべて並べた後、最初に定位置になかった正数が答えになります。
重複する数字がないので、for文で最初から見て、入力の数字を並び替えた後に居るはずの位置にスワップします。
そうすることでO(n)内でのソートが可能となります。

今日は以上。
よいプログラミング生活を！