Respectable
MinAvgTwoSlice
少なくとも2つの要素を含むスライスの最小平均を見つけます。
タスク説明
N個の整数で構成される空でない配列Aが与えられます。 0≤P<Q <Nのような整数のペア（P、Q）は、配列Aのスライスと呼ばれます（スライスには少なくとも2つの要素が含まれていることに注意してください）。スライスの平均（P、Q）は、A [P] + A [P + 1] + ... + A [Q]の合計をスライスの長さで割ったものです。正確には、平均は（A [P] + A [P + 1] + ... + A [Q]）/（Q − P + 1）に等しくなります。
たとえば、次のような配列A：
例
A [0] = 4
A [1] = 2
A [2] = 2
A [3] = 5
A [4] = 1
A [5] = 5
A [6] = 8
次のサンプルスライスが含まれています。
- スライス（1、2）、その平均は（2 + 2）/ 2 = 2;
- スライス（3、4）、その平均は（5 + 1）/ 2 = 3;
- スライス（1、4）、その平均は（2 + 2 + 5 + 1）/ 4 = 2.5です。
目標は、平均が最小であるスライスの開始位置を見つけることです。
関数を書く：
class solution {public int solution(int [] A); }
これは、N個の整数で構成される空でない配列Aが与えられた場合、最小の平均でスライスの開始位置を返します。平均が最小のスライスが複数ある場合は、そのようなスライスの最小の開始位置を返す必要があります。
たとえば、次のような配列Aが与えられます。
例
A [0] = 4
A [1] = 2
A [2] = 2
A [3] = 5
A [4] = 1
A [5] = 5
A [6] = 8
上で説明したように、関数は1を返す必要があります。
次の仮定のための効率的なアルゴリズムを記述します。
- Nは[2..100,000]の範囲内の整数です。
- 配列Aの各要素は、[-10,000..10,000]の範囲内の整数です。
解く
Program
MinAvgTwoSliceSolution.java
public int solution(int[] A) {
int goal = 0;
int[] P = new int[A.length + 1];
P[0] = 0;
for (int i = 0; i < A.length; i++) {
P[i + 1] = P[i] + A[i];
}
double minAvg = 10000;
for(int j = 0; j < A.length - 1; j++) {
double currentAvg2 = (double)(P[j + 2] - P[j]) / 2;
if (currentAvg2 < minAvg) {
minAvg = currentAvg2;
goal = j;
}
if (j == A.length - 2) break;;
double currentAvg3 = (double)(P[j + 3] - P[j]) / 3;
if (currentAvg3 < minAvg) {
minAvg = currentAvg3;
goal = j;
}
}
return goal;
}
Detected time complexity:
O(N)
jUnit
MinAvgTwoSliceSolutionTest.java