最低平均两片Codility [英] Min Average Two Slice Codility
问题描述
给出了由N个整数组成的非空零索引数组A.一对整数（P，Q），使得0≤P<1。 Q< N，被称为数组A的切片（注意切片包含至少两个元素）。切片（P，Q）的平均值是A [P] + A [P + 1] + ... + A [Q]之和除以切片的长度。确切地说，平均值等于（A [P] + A [P + 1] + ... + A [Q]）/（Q - P + 1）。
例如，数组如此：
A non-empty zero-indexed array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P < Q < N, is called a slice of array A (notice that the slice contains at least two elements). The average of a slice (P, Q) is the sum of A[P] + A[P + 1] + ... + A[Q] divided by the length of the slice. To be precise, the average equals (A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1).
For example, array A such that:
A[0] = 4
A[1] = 2
A[2] = 2
A[3] = 5
A[4] = 1
A[5] = 5
A[6] = 8
包含以下示例切片：
contains the following example slices:
- 切片（1,2），平均值为（2 + 2）/ 2 = 2;
- 切片（3,4），平均值为（5 + 1） ）/ 2 = 3;
- 切片（1,4），平均值为（2 + 2 + 5 + 1）/ 4 = 2.5。
目标是找到平均值最小的切片的起始位置。
The goal is to find the starting position of a slice whose average is minimal.
写一个函数：
class Solution { public int solution(int[] A); }
给定一个由N个整数组成的非空零索引数组A，返回起始值具有最小平均值的切片的位置。如果有多个切片具有最小平均值，则应返回此切片的最小起始位置。
例如，给定数组A使得：
that, given a non-empty zero-indexed array A consisting of N integers, returns the starting position of the slice with the minimal average. If there is more than one slice with a minimal average, you should return the smallest starting position of such a slice.
For example, given array A such that:
A[0] = 4
A[1] = 2
A[2] = 2
A[3] = 5
A[4] = 1
A[5] = 5
A[6] = 8
该函数应返回1，如上所述。
the function should return 1, as explained above.
假设：
- N是[2..100,000]范围内的整数;
- 数组A的每个元素都是[-10,000范围内的整数。 .10,000]。
复杂性：
- 预期最坏情况时间复杂度为O（N）;
- 预期最坏情况空间复杂度为O（N），超出输入存储（不计入输入参数所需的存储）。
可以修改输入数组的元素。
Elements of input arrays can be modified.
这是我最好的解决方案，但就时间而言显然不是最优的复杂。
任何想法？
This is my best solution, but obviously not optimal in terms of time complexity.
Any ideas?
public int solution(int[] A) {
int result = 0;
int N = A.length;
int [] prefix = new int [N+1];
for (int i = 1; i < prefix.length; i++) {
prefix[i] = prefix[i-1] + A[i-1];
}
double avg = Double.MAX_VALUE;
for (int i = 1; i < N; i++) {
for (int j = i+1; j <=N; j++) {
double temp = (double)(prefix[j]-prefix[i-1]) /(double)(j-i+1);
if (temp < avg) {
avg = temp;
result = i-1;
}
}
}
return result;
}
https://codility.com/demo/results/demo65RNV5-T36/
推荐答案
我几天前发布了这个：
检查出来：
Check this out:
http://codesays.com/2014/solution -to-min-avg-two-slice-by-codility /
在那里，他们详细解释了为什么他们的解决方案有效。我b $ b还没有实现它，但我一定会尝试。
In there, they explain with great detail why their solution works. I haven't implemented it myself yet, but I will definitely try it.
希望它有所帮助！
但我刚看到它被主持人删除了。他们说这个链接已经死了，但我只是尝试过它并且工作正常。我再次发布它，希望可以验证链接是否正常。
but I just saw it was deleted by a moderator. They say the link is dead, but I just tried it and it works fine. I'm posting it once again, hoping it can be validated that the link is good.
现在我也可以提供我的实现，基于我的代码链接之前提供： https://codility.com/demo/results/demoERJ4NR-ETT/
And now I can also provide my implementation, based on the codesays link that I provided before: https://codility.com/demo/results/demoERJ4NR-ETT/
干杯！
这篇关于最低平均两片Codility的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
