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