Painless
FrogRiverOne
Find the earliest time when a frog can jump to the other side of a river.
タスク説明
小さなカエルが川の向こう側に行きたがっています。カエルは最初は川の一方の土手（位置0）にあり、反対側の土手（位置X + 1）に行きたいと思っています。葉が木から川の水面に落ちます。
落ち葉を表すN個の整数で構成される配列Aが与えられます。 A [K]は、時間Kで1枚の葉が落ちる位置を秒単位で表します。
目標は、カエルが川の反対側にジャンプできる最も早い時間を見つけることです。カエルは、川の1からXまでのすべての位置に葉が現れる場合にのみ交差できます（つまり、1からXまでのすべての位置が葉で覆われている最も早い瞬間を見つけたい）。川の流れの速度は無視できるほど小さいと考えることができます。つまり、葉が川に落ちると、葉の位置は変わりません。
たとえば、次のような整数X = 5と配列Aが与えられます。
A [0] = 1
A [1] = 3
A [2] = 1
A [3] = 4
A [4] = 2
A [5] = 3
A [6] = 5
A [7] = 4
2番目の6では、葉が位置5に落ちます。これは、川の向こう側のすべての位置に葉が現れる最も早い時間です。
関数を書く：
class solution {public int solution（int X、int [] A）; }
これは、N個の整数と整数Xで構成される空でない配列Aが与えられた場合、カエルが川の反対側にジャンプできる最も早い時間を返します。
カエルが川の反対側にジャンプできない場合、関数は-1を返す必要があります。
たとえば、X = 5で、配列Aが次のようになっているとします。
A [0] = 1
A [1] = 3
A [2] = 1
A [3] = 4
A [4] = 2
A [5] = 3
A [6] = 5
A [7] = 4
上で説明したように、関数は6を返す必要があります。
次の仮定のための効率的なアルゴリズムを記述します。
- NとXは、[1..100,000]の範囲内の整数です。
- 配列Aの各要素は、[1..X]の範囲内の整数です。
解く
Program
public int solution(int X, int[] A) {
int goal = -1;
int B[] = new int[X + 1];
java.util.Arrays.fill(B, -1);
for (int i = 0; i < A.length; i++) {
if (B[A[i]] < 0 || B[A[i]] > i) {
B[A[i]] = i;
}
}
for (int j = 1; j < B.length; j ++) {
int anB = B[j];
if (anB < 0) {
goal = -1;
break;
} else {
goal = goal < anB ? anB : goal;
}
}
return goal;
}
Detected time complexity:
O(N)
jUnit
Report
Candidate Report: training933GQH-AM9