[解決済み] 与えられた数列の中に現れない最小の正の整数を求めよ。

質問

以下のCodilityで問題を解決しようとしています。

関数を書いてください。

class Solution { public int solution(int[] A); }

N 個の整数の配列 A が与えられたとき、A に含まれない最小の正の整数（0 より大きい）を返すもの。

例えば、A = [1, 3, 6, 4, 1, 2]とすると、この関数は5を返すはずです。

Given A = [1, 2, 3], the function should return 4.

Given A = [−1, −3], the function should return 1.

と仮定する。

Nは[1..100,000]の範囲にある整数である。 配列Aの各要素は [-1,000,000..1,000,000] の範囲にある整数である。 複雑である。

最悪の場合の予想時間計算量はO(N)である。 予想される最悪の場合の空間の複雑さはO(N) (入力引数のために必要なストレージは考慮しない)です。

以下の解答を書くと、低い性能になりますが、バグが見当たりません。

public static int solution(int[] A) {

        Set<Integer> set = new TreeSet<>();

        for (int a : A) {
            set.add(a);
        }

        int N = set.size();

        int[] C = new int[N];

        int index = 0;

        for (int a : set) {
            C[index++] = a;
        }

        for (int i = 0; i < N; i++) {

            if (C[i] > 0 && C[i] <= N) {
                C[i] = 0;
            }
        }

        for (int i = 0; i < N; i++) {

            if (C[i] != 0) {
                return (i + 1);
            }
        }

        return (N + 1);
    }

スコアはここで提供されます。

今後も自分で調べてみますが、もっとよく見えるようでしたらお知らせください。

解決方法は？

予想される実行時間がリニアであるべきなら TreeSet は、入力をソートするため O(NlogN) . したがって HashSet を必要とする。 O(N) を追加する時間 N 要素を使用します。

それに、4つのループは必要ありません。正の入力要素をすべて HashSet (1回目のループ)、そしてそのSetに含まれない最初の正の整数を見つける(2回目のループ)。

int N = A.length;
Set<Integer> set = new HashSet<>();
for (int a : A) {
    if (a > 0) {
        set.add(a);
    }
}
for (int i = 1; i <= N + 1; i++) {
    if (!set.contains(i)) {
        return i;
    }
}