最低平均两片Codility
给出了由N个整数组成的非空零索引数组A. 一对整数（P，Q），使得0≤P<Q <N，被称为阵列A的切片（注意该切片包含至少两个元素）。 切片（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]范围内的整数。
复杂：
- 预期的最坏情况时间复杂度是O（N）;
- 预期的最坏情况空间复杂度是O（N），超出输入存储（不计入输入参数所需的存储）。
可以修改输入数组的元素。
这是我最好的解决方案，但在时间复杂度方面显然不是最优的。
有任何想法吗？
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/
几天前我发布了这个post：
看一下这个：
http://codesays.com/2014/solution-to-min-avg-two-slice-by-codility/
在那里，他们详细解释了为什么他们的解决方案有效。 我自己还没有实现它，但我肯定会尝试它。
希望能帮助到你！
但我刚看到它被主持人删除了。 他们说这个链接已经死了，但我只是尝试过它并且工作正常。 我再次发布它，希望可以validation链接是好的。
现在我也可以根据我之前提供的codesays链接提供我的实现： https ：//codility.com/demo/results/demoERJ4NR-ETT/
干杯!
棘手的部分是在你开始编码之前弄清楚确定平均最小切片的长度为2或3.从那里它更容易，但我有一些重要的注意事项：
-
你根本不需要除法，你可以相乘，这样你就可以在一片长度为6的情况下获得相同的平均值并完全避免浮点运算
-
你不需要在循环中进行除法（或者在我的情况下是乘法），最后一次就足够了。
-
如果您必须实际执行此操作，则应始终比较两个浮点数，如下所示：EPSILON = 0.0000001（取决于您查找的精度可能是不同的数字），如果Math.abs（averageTwo – averageThree）
这是我在Java中的解决方案，它在Codility上得到100％：
public int solution(int[] A) { if (A.length == 2) return 0; int minSliceTwo = A[0] + A[1]; int minTwoIndex = 0; int minSliceThree = Integer.MAX_VALUE; int minThreeIndex = 0; for (int i = 2; i < A.length; i++) { int sliceTwo = A[i - 1] + A[i]; if (sliceTwo < minSliceTwo) { minSliceTwo = sliceTwo; minTwoIndex = i - 1; } int sliceThree = sliceTwo + A[i - 2]; if (sliceThree < minSliceThree) { minSliceThree = sliceThree; minThreeIndex = i - 2; } } int averageMinTwo = minSliceTwo*3; int averageMinThree = minSliceThree*2; if (averageMinTwo == averageMinThree) return Math.min(minTwoIndex, minThreeIndex); else return averageMinTwo < averageMinThree ? minTwoIndex : minThreeIndex; }
据我所知， http：//www.rationalplanet.com/php-related/minavgtwoslice-demo-task-at-codility-com.html提供了迄今为止我所知的最佳解释和解决方案。 由于这是在前缀sum部分下面，以下是我试图熟悉前缀sum方法的那个。
function solution($A) { // write your code in PHP5.3 $N = count($A); if ($N > 100000 || $N < 2 ) { return -1; } elseif ($N === 2) { return 0; } $presum = array(); $presum[] = 0; $mavg = PHP_INT_MAX; $index = 0; for ($i = 0; $i < $N; $i++) { $presum[$i+1] = $A[$i] + $presum[$i]; } for ($i = 0; $i < $N-2; $i++) { for ($j = $i+1; $j < $i + 3; $j++ ) { $avg = ($presum[$j+1] - $presum[$i]) / ($j - $i + 1); if ($mavg > $avg) { $mavg = $avg; $index = $i; } } } $avg = ($presum[$N] - $presum[$N-2]) / 2; if ($mavg > $avg) { $index = $N - 2; } return $index; }
100％得分。 的JavaScript。
var min_pos = 0; var min = Number.MAX_VALUE; function solution(A) { for (var a = 0; a < A.length - 2; a++) { process((A[a] + A[a + 1]) / 2.0, a); process((A[a] + A[a + 1] + A[a + 2]) / 3.0, a); } process((A[A.length - 2] + A[A.length - 1]) / 2.0, A.length - 2); return min_pos; } function process(val, a) { if (val < min) { min_pos = a; min = val; } else if (val === min && a < min_pos) { min_pos = a; } }
这是使用前缀sums的另一个Java解决方案100/100：
public int solution(int[] A) { int len = A.length, result = len - 1, sum = 0; int[] prefixSums = new int[len + 1]; for (int i = 1; i <= len; ++i) { prefixSums[i] = prefixSums[i-1] + A[i-1]; } double min = Double.MAX_VALUE, average = 0d; for (int P = 0, Q = 1; Q + 1 < prefixSums.length; ++P, ++Q ) { sum = prefixSums[Q + 1] - prefixSums[P]; average = (sum)/(double) 2; if (average < min) { min = average; result = P; } if ( Q + 2 < prefixSums.length ) { sum = prefixSums[Q + 2] - prefixSums[P]; average = (sum)/(double) 3; if (average < min) { min = average; result = P; } } } return result; }
这是密码链接： https ：//codility.com/demo/results/demo4S4VJX-WMJ/
这是一个有效的前缀和实现（100％在Codility中）：
import sys def solution(A): n = len(A) pre_sum = [0] * (n+1) min_slice_avg = sys.maxint min_slice_idx = 0 for i in xrange(1,n+1): pre_sum[i] = pre_sum[i-1] + A[i-1] # calculate at least 2 prefix sums if i-2 < 0: continue # check prev 3 slices if we have calculated 3 prefix sums if i>=3: prev_3_slice_avg = (pre_sum[i] - pre_sum[i-3]) / 3.0 if prev_3_slice_avg < min_slice_avg: min_slice_avg = prev_3_slice_avg min_slice_idx = i-3 # check prev 2 slices prev_2_slice_avg = (pre_sum[i] - pre_sum[i-2]) / 2.0 if prev_2_slice_avg < min_slice_avg: min_slice_avg = prev_2_slice_avg min_slice_idx = i-2 return min_slice_idx
100％正确性和性能（java）
void sumArray(int[] A, int[] sum) { for (int i = 1; i < sum.length; i++) { sum[i] = sum[i - 1] + A[i - 1]; } } int getTotalSum(int[] sum, int start, int last) { return sum[last + 1] - sum[start]; } double minav = Double.MAX_VALUE; int minind = Integer.MAX_VALUE; public int solution(int[] A) { int[] sum = new int[A.length + 1]; sumArray(A, sum); int startpos = 0; for (int i = 1; i <= 2; i++) { startpos = 0; while (startpos + i < A.length) { double suma = getTotalSum(sum, startpos, startpos + i); double size = (startpos + i) - startpos + 1; double av = suma / size; if (av <= minav) { if (av < minav || startpos < minind) { minind = startpos; } minav = av; } startpos += 1; } } return minind; }
这是一个数学问题……要解决这个问题，你必须要理解切片平均值之间存在的关系。
我们从问题描述中知道切片的最小长度为2.这个问题的技巧是最小平均切片也不能长于3.所以我们只需要计算长度为2和3的切片的平均值。
要理解为什么最小平均切片不能超过3，考虑它长于3的情况……
ex. [-10, 3, 4, -20] avg(0,3) = -23 / 4 = -5.75 // entire array is -5.75 average avg(0,1) = -7 / 2 = -3.5 // subslice (0,1) avg(2,3) = -16 / 2 = -8 // subslice (2,3)
请注意(avg(0,1) + avg(2,3)) / 2 = avg(0,3)因此，如果avg(0,1) != avg(2,3)那么其中一个必须更小比另一个。
无论我们分割这个数组的方式是什么，如果切片不完全相同，那么其中一个必须具有比完整切片更低的平均值。 玩弄它，你会发现它是真的。 那里有数学certificate。
static public int solution(int[] A) { // write your code in Java SE 8 float avg = 0f; int min_index = 0; int P = 0; //formula float sums[] = new float[A.length ]; //sufffix sums int prefix = 0; for (int i = 0; i < A.length; i += 1) { prefix += A[i]; sums[i] += prefix; } float min_avg = Float.MAX_VALUE; for (int i = 1; i < A.length; i++) { avg = (sums[i] - sums[P] + A[P]) / (i - P + 1); if (avg < min_avg) { min_avg = avg; min_index = P; }
这个想法很简单，但不是那么简单， A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1)就是那里的公式，首先计算前缀和。
公式：min_avg =（前缀[i] - 前缀[P] + A [P]）/（i - P + 1）'
if (A[i] < min_avg) { P = i; } } return min_index; }
虽然这似乎是一个有点受欢迎的问题，但根据有多少人已经发布了他们的代码，我对2/3元素的子系统解决方案不满意（来吧！谁会在采访期间想到这一点） ？），也没有解释（或缺乏解释）。
所以我继续寻找其他方法。 我找到了关于最大子arrays问题（MSP）的Kanade算法 ，然后想到了一个不同的解决方案。
基本问题是（类似于MSP）： 包含第i个元素的切片的最小平均值是多少？
为了回答这个问题，我们将寻找以第i个元素结尾的切片，只更新它们的左索引。 也就是说，我们必须检查切片A[lft_idx : i] 。
假设我们知道切片A[lft_idx : i - 1]具有最小平均值，那么我们有两种可能性：
-
A[lft_idx : i]的平均值是最小的。 -
A[i - 1 : i]的平均值最小（最短切片有2个元素）。
在案例1中发生的是我们继续增长从lft_idx开始的切片。
然而，在第2种情况下，我们发现增加前一个切片实际上会增加平均值。 所以我们重新开始并将切片的开始（ lft_idx ）“重置”到前一个元素（ i - 1 ）。 现在我们有一个新的最佳切片大小2从这一点开始增长。
最后，我们想要全局最小平均值，所以我们需要跟踪到目前为止的最小值和它开始的位置（问题只是要求这个，但我们也可以保存正确的索引）。
int solution(vector &A) { // Find prefix sum. int N = A.size(); vector ps(N + 1, 0); for (int i = 1; i <= N; i++) { ps[i] = A[i - 1] + ps[i - 1]; } int lft_idx, min_lft_idx; double avg_here, min_avg, avg_of_two, avg_with_prev; // Initialize variables at the first possible slice (A[0:1]). lft_idx = min_lft_idx = 0; avg_here = min_avg = (A[0] + A[1]) / 2.0; // Find min average of every slice that ends at ith element, // starting at i = 2. for (int i = 2; i < N; i ++) { // average of A[lft_idx : i] avg_with_prev = ((double) ps[i + 1] - ps[lft_idx]) / (i - lft_idx + 1); // average of A[i - 1 : i] avg_of_two = (A[i - 1] + A[i]) / 2.0; // Find minimum and update lft_idx of slice // (previous lft_idx or i - 1). if (avg_of_two < avg_with_prev) { avg_here = avg_of_two; lft_idx = i - 1; } else avg_here = avg_with_prev; // Keep track of minimum so far and its left index. if (avg_here < min_avg) { min_avg = avg_here; min_lft_idx = lft_idx; } } return min_lft_idx; }
注意：我在这里使用前缀和来计算切片平均值，因为这是问题出现在Codility中的地方，但它可以很容易地被一个变量替换，该变量具有前一个切片的大小和另一个乘法。
用PHP编写的我的100/100分数解决方案http://www.rationalplanet.com/php-related/minavgtwoslice-demo-task-at-codility-com.html
我的答案得分为100分
public class MinAvgTwoSlice { public static void main(String[] args) { System.out.println(new MinAvgTwoSlice().solution(new int[] {4, 2, 2, 5, 1, 5, 8} )); } public int solution(int[] A) { double minAvg = 100000; int index=0; if(A.length<=2) { return 0; } for(int i=0;i
谢谢：基于codesays.com提供的逻辑
这是我用C编写的解决方案（得分100％）
#include int solution(int A[], int N) { // write your code in C99 int *p, i; float minAvg, tmpAvg; int index=0; p=malloc(sizeof(int)*(N+1)); memset(p, 0, sizeof(int)*(N+1)); if(N == 2) { return 0; } *p=0; //Building prefixes vector for(i=0;i
public int solution(int[] A) { //C# solution thats getting 100%. Once you find min avg with always within 2 //or 3 elements of moving index its much simpler sol int minIndex = 0; double minAvgVal = Double.MaxValue; for (int i = 0; i < A.Length-2; i++) { double twoDigitMin = (A[i] + A[i + 1])/2.0; if (minAvgVal > twoDigitMin) { minAvgVal = twoDigitMin; minIndex = i; } double threDigitMin = (A[i] + A[i + 1] + A[i+2]) / 3.0; if (minAvgVal > threDigitMin) { minAvgVal = threDigitMin; minIndex = i; } } double last2Avg = (A[A.Length - 2] + A[A.Length - 1])/2.0; if (minAvgVal > last2Avg) { minIndex = A.Length - 2; } return minIndex; }
我在C＃中得到了100％。 试试这个https://codility.com/demo/results/demoV25DUE-9A8 。
public static int solution(int[] A) { float min_avg = (A[0] + A[1]) / 2; int minpos = 0; for (int i = 0; i < A.Length-2; i++) { float firsttwo = (float)(A[i] + A[i+1])/2; if (firsttwo < min_avg) { min_avg = firsttwo; minpos = i; } float three = (float)(A[i] + A[i+1] + A[i+2])/3; if (three < min_avg) { min_avg = three; minpos = i; } float lasttwo = (float)(A[i + 1] + A[i + 2]) / 2; if (lasttwo < min_avg) { min_avg = lasttwo; minpos = i+1; } } return minpos; }
这是Go实现：
func Solution(A []int) int { if len(A) < 2 { return -1 } result := 0 minAvg := float64(A[0]+A[1]) / 2 var curAvg float64 for index := 0; index < len(A)-2; index++ { curAvg = float64(A[index]+A[index+1]) / 2 if curAvg < minAvg { minAvg = curAvg result = index } curAvg = float64(A[index]+A[index+1]+A[index+2]) / 3 if curAvg < minAvg { minAvg = curAvg result = index } } curAvg = float64(A[len(A)-2]+A[len(A)-1]) / 2 if curAvg < minAvg { minAvg = curAvg result = len(A) - 2 } return result }
private static int solution(int[] a) { // TODO Auto-generated method stub int sum=0; int absSum=0; int minAbsSlice=10000; for(int i=0;i=i){ absSum=sum+a[j]; if(absSum
这是我在C ++中的解决方案，基于certificate最小切片必须存在长度为2或3，请参见https://codesays.com/2014/solution-to-min-avg-two-slice-by-codility/
在Codility上得到100％的正确性和速度得分。 无需分配任何内存来解决此问题，因此算法空间为O（1），不计算输入向量。
int solution(vector &A) { int N = A.size(); int minSliceStart = 0; if (N > 2) { // Min Slice must be of length 2 or 3. // If Min Slice is longer, // it must be divisible into smaller parts of equal average int min_2_slice_start = 0; int min_3_slice_start = 0; int min_2_slice_sum = A[0]+A[1]; int min_3_slice_sum = A[0]+A[1]+A[2]; for(int i=0; i<(N-1); i++) { int cur_2_slice_sum = A[i]+A[i+1]; // check if the current 2-slice sum is smaller if (cur_2_slice_sum < min_2_slice_sum) { min_2_slice_sum = cur_2_slice_sum; min_2_slice_start = i; } // check if the current 3-slice sum is smaller if (i<(N-2)) { int cur_3_slice_sum = A[i]+A[i+1]+A[i+2]; if (cur_3_slice_sum < min_3_slice_sum) { min_3_slice_sum = cur_3_slice_sum; min_3_slice_start = i; } } } #ifdef Want_Debug_Statements cout << "2-Slice: start=" << min_2_slice_start << ", sum=" << min_2_slice_sum <
python 100％：
def solution(A): if(len(A) < 2): return 0; MinAvg=float(A[0]+A[1])/float(2); Index=0; for nn in range(1,len(A)-1): Avg=float(A[nn]+A[nn+1])/float(2); if(Avg
为了解释：
对2个连续元素进行平均和比较几乎得到最大分数。 因为当一个元素添加元素时，如果平均值较小，那么接下来的两个元素将具有较小的平均值。
之后只剩下3个元素的例外，如[-1,2,4，-1,2，-1]。
这是我在Java中的实现。 我得到了100％。 该算法是相同的（2和3个连续值的总和），除了我没有使用addidional内存作为前缀和。 我们不需要一次性所有的总和，因此我们只能保持当前的总和，并且当我们向右时，从总和中减去最左边的元素。
public int solution(int vect[]) { double minAvg = (vect[0] + vect[1]) / 2.; int minIndex = 0; double tempAvg = minAvg; int tempSum = vect[0] + vect[1]; int tempIndex = 0; int tempLength = 2; double newAvg; int newSum, newIndex; for(int j=2; j minAvg && j-tempIndex>1) { tempIndex = j; tempLength = 1; tempSum = vect[j]; } } return minIndex; }
我认为检查长度为2和3的切片背后有逻辑。根据问题陈述，切片的最小长度可以是2。
因此，在切片增长到2个最小长度切片之前，我们可以添加到切片的最小元素是1.所以我们必须检查长度为2和3的切片。我们不需要超出切片长度3，因为它最终会有2片长度2。
让我们再看一个例子，假设Slice的长度最小为3.现在在这种情况下，根据我们的公式，我们需要从长度为3到5的切片进行检查。考虑以下数组
-30，-1，-1，-1，-30，-1，-1,1,2,3,4,45
在这里，如果我们采用Slice（0,4），则平均值为-12.6（这是最小值）。 尝试所有其他组合（长度3和4）并围绕它玩。 你会明白的。
如果我们采用长度为6的切片然后切片（0,5），平均值为-10.66，等于切片（0,2）和切片（3,5）的平均值
不使用前缀总和的解决方案（100％分数）
public int solution(int[] A) { float tempAverage,finalAverage = Float.MAX_VALUE; int startLocation = 0; int lengthOfTheSlice = 0; for(int i=0; i < A.length -1; ++i) { tempAverage = (float)(A[i] + A[i+1])/2; if(tempAverage < finalAverage) { finalAverage = tempAverage; startLocation = i; lengthOfTheSlice =2; } } for(int i=0; i < A.length -2; ++i) { tempAverage = (float)(A[i] + A[i+1]+ A[i+2])/3; if(tempAverage < finalAverage) { finalAverage = tempAverage; startLocation = i; lengthOfTheSlice =3; } } System.out.print("Length of the slice \t"+lengthOfTheSlice); return startLocation; }
C ++解决方案，对我来说很好
int solution(vector &A) { // write your code in C++14 (g++ 6.2.0) if(A.size() < 2) return 0; int min_index = 0; double min = (A[0] + A[1]) / 2; for(unsigned int i = 2; i < A.size(); i++){ double temp_three = (A[i - 2] + A[ i - 1] + A[i]) / 3.0; double temp_two = (A[ i - 1] + A[i]) / 2.0; if(temp_three < min){ min = temp_three; min_index = i - 2; } if(temp_two < min){ min = temp_two; min_index = i - 1; } } return min_index; }