Respectable
MinAvgTwoSlice
Find the minimum average of slices that contain at least two elements.
Given a non-empty array A consisting of N integers. A pair of integers (P, Q) such as 0 ≤ P <Q <N is called a slice of array A (note that the slice contains at least two elements). The average slice (P, Q) is the sum of A [P] + A [P + 1] + ... + A [Q] divided by the slice length. To be precise, the mean is equal to (A [P] + A [P + 1] + ... + A [Q])/(Q − P + 1).
For example, the following array A:
Example
A [0] = 4
A [1] = 2
A [2] = 2
A [3] = 5
A [4] = 1
A [5] = 5
A [6] = 8
The following sample slices are included.
The goal is to find the starting position of the slice with the smallest average.
Write a function:
class solution {public int solution(int [] A); }
It returns the starting position of the slice with the smallest average given a non-empty array A consisting of N integers. If you have multiple slices with the lowest average, you need to return the smallest starting position for such slices.
For example, given the following array A:
Example
A [0] = 4
A [1] = 2
A [2] = 2
A [3] = 5
A [4] = 1
A [5] = 5
A [6] = 8
As explained above, the function must return 1.
Write an efficient algorithm for the following assumptions:
Program MinAvgTwoSliceSolution.java
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
Report trainingP37RME-WBC
Recommended Posts