Painless

PermMissingElem

指定された順列で欠落している要素を見つけます。

タスク説明

N個の異なる整数で構成される配列Aが与えられます。配列には[1 ..（N + 1）]の範囲の整数が含まれています。これは、1つの要素が欠落していることを意味します。

あなたの目標は、その欠けている要素を見つけることです。

関数を書く：

class solution {public int solution（int [] A）; }

配列Aが与えられると、欠落している要素の値を返します。

たとえば、次のような配列Aが与えられます。

   A [0] = 2
   A [1] = 3
   A [2] = 1
   A [3] = 5

欠落している要素であるため、関数は4を返す必要があります。

次の仮定のための効率的なアルゴリズムを記述します。

Nは[0..100,000]の範囲内の整数です。
Aの要素はすべて別個のものです。
配列Aの各要素は、[1 ..（N + 1）]の範囲内の整数です。

解く

Program【案１：Arrays.sort】

PermMissingElemSolutionSort.java

PermMissingElemSolutionSort.java

    public int solution(int[] A) {
        if (A.length == 0) return 1;

        java.util.Arrays.sort(A);
        for (int i = 0; i < A.length; i++) {
            if ((i + 1) != A[i]) return i + 1;
        }
        return A.length + 1;
    }

Detected time complexity:
O(N) or O(N * log(N))

jUnit

PermMissingElemSolutionSortTest.java

Program【案２: data bucket】

PermMissingElemSolutionBucket.java

PermMissingElemSolutionBucket.java

    public int solution(int[] A) {
        boolean[] bucket = new boolean[100000 + 2];
        java.util.Arrays.fill(bucket, false);
        for (int anA : A) {
            bucket[anA] = true;
        }
        for (int i = 1; i < bucket.length; i++) {
            if (!bucket[i]) {
                return i;
            }
        }

        return 1;
    }

Detected time complexity:
O(N) or O(N * log(N))

jUnit

PermMissingElemSolutionBucketTest.java

See also: CodilityのLessonsをすべて解く（更新中）