最小平均兩個切片編碼

Question

給出了一個由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); } 

，鑑於非空零索引的數組A由N個整數的，返回具有最小平均切片的起始位置。如果有多個平均值最小的切片，則應返回此切片的最小起始位置。
例如，給定陣列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/

Answer 1

我這個前幾天發佈：

Check this out:

http://codesays.com/2014/solution-to-min-avg-two-slice-by-codility/

In there, they explain with great detail why their solution works. I haven't implemented it myself yet, but I will definitely try it.

Hope it helps!

，但我只看到它是由一個刪除主持人。他們說這個鏈接已經死了，但我只是試了一下而且效果很好。我再次發佈它，希望可以驗證鏈接是否正常。

現在我還可以提供我的實現的基礎上，codesays鏈接，我以前提供：https://codility.com/demo/results/demoERJ4NR-ETT/

乾杯！

Answer 2

我100/100用PHP編寫的得分液http://www.rationalplanet.com/php-related/minavgtwoslice-demo-task-at-codility-com.html

Answer 3

我與評分回答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<A.length-2;i++) { 

     if((A[i]+A[i+1])/2.0<minAvg) { 
      minAvg=(A[i]+A[i+1])/2.0; 
      index=i; 
     } 

     if((A[i]+A[i+1]+A[i+2])/3.0<minAvg) { 

      minAvg=(A[i]+A[i+1]+A[i+2])/3.0; 
      index=i; 
     } 
    } 

    int aMax = A.length-2; 

    if((A[aMax]+A[aMax+1])/2.0<minAvg) { 

     minAvg=(A[aMax]+A[aMax+1])/2.0; 
     index=aMax; 
    } 

    return index; 
} 
} 

感謝：基於對codesays.com提供的邏輯

Answer 4

這裏有一個前綴和實施，工程（在Codility 100％）：

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 

Answer 5

據我所知，http://www.rationalplanet.com/php-related/minavgtwoslice-demo-task-at-codility-com.html提供了迄今爲止我所知道的最佳解釋和解決方案。 由於這是在前綴總和部分，以下是我試圖熟悉前綴總和方法。

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; 
} 

Answer 6

棘手的部分是要弄清楚你開始編碼，有長度爲2或3 從那裏很容易的確保的平均分片甚至過，但我有幾個重要事項：

1. 你不需要師可言，你可以代替大量繁殖，這樣就可以得到在長度爲6片相同的平均，避免浮點運算完全

2. 你不需要師（或在我的情況下乘法）在th e循環，一次到底就足夠了。

3. 如果你要真正做到這一點，你應該總是比較兩個浮點數像這樣： EPSILON = 0.0000001（取決於你看這個精度也得到不同數量），如果Math.abs（averageTwo - averageThree）< EPSILON它意味着它們是平等的。而且你不需要雙精度，浮點就足夠了。

這是我在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; 
} 

Answer 7

這是我的解決方案用C寫的（得分100％）

#include <string.h> 

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<N;i++) { 
     *(p+i+1)=*(p+i)+A[i]; 
    } 

    minAvg=*(p+N)/(float)(N); 

    for(i=0; i<N-1; i++) { 
     tmpAvg=(*(p+i+2)-*(p+i))/(float)(2); 
     if (tmpAvg < minAvg) { 
      minAvg=tmpAvg; 
      index=i; 
     } 
    } 

    for(i=0; i<N-2; i++) { 
     tmpAvg=(*(p+i+3)-*(p+i))/(float)(3); 
     if (tmpAvg < minAvg) { 
      minAvg=tmpAvg; 
      index=i; 
     } 
    } 

    free(p); 
    return index; 
} 

Answer 8

這裏是一個執行：

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 
} 

Answer 9

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; 
     } 

Answer 10

這裏還有一個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; 
    } 

這裏的codility鏈接：https://codility.com/demo/results/demo4S4VJX-WMJ/

Answer 11

我在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; 
    } 

Answer 12

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; 
} 

Answer 13

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; 
    } 
} 

Answer 14

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<a.length;i++){ 
     sum=a[i]; 
     for(int j=1;j<a.length;j++){ 
      if(j>=i){ 
       absSum=sum+a[j]; 
       if(absSum<sum){ 
        sum=absSum; 
        absSum=Math.abs(absSum); 

       }else{ 

        absSum=Math.abs(sum); 
        sum=absSum; 
       } 
      } 
     } 
     sum=0; 
     if(minAbsSlice<absSum){ 
      minAbsSlice=minAbsSlice; 
     }else{ 
      minAbsSlice=absSum; 
     } 

    } 
    return minAbsSlice; 
} 

Answer 15

這是我在C++溶液基於證明最小片必須用長度爲2或3存在，見證明在https://codesays.com/2014/solution-to-min-avg-two-slice-by-codility/

得到的分數的100％Codility的正確性和速度。不需要分配任何內存來解決這個問題，因此算法的空間是O（1），不計算輸入向量。

int solution(vector<int> &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 <<endl; 
      cout << "3-Slice: start=" << min_3_slice_start << ", sum=" << min_3_slice_sum <<endl; 
     #endif 

     // If 2-slice or 3-slice are equal, take the first one. 
     // Note: rather than computing averages by dividing, 
     // multiple each side by the other denominator instead & compare. 
     if (min_2_slice_sum*3 == min_3_slice_sum*2) { 
      if (min_2_slice_start < min_3_slice_start) 
       minSliceStart = min_2_slice_start; 
      else 
       minSliceStart = min_3_slice_start; 
     } else { 
      if (min_2_slice_sum*3 < min_3_slice_sum*2) 
       minSliceStart = min_2_slice_start; 
      else 
       minSliceStart = min_3_slice_start; 
     } 
    } 

    return minSliceStart; 
} 

Answer 16

這是一個數學問題......要解決這個問題，你必須瞭解切片平均值之間的關係。

我們從問題描述中知道切片的最小長度是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)那麼他們中的一個必須小於其他。

不管我們分割這個數組，如果這些切片不完全相同，那麼其中一個切片的平均值必須比全切片要低。玩弄它，你會發現它是真的。那裏有數學證明。

Answer 17

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)公式那裏，首先計算前綴款項。在python

formula: min_avg = (prefix[i] - prefix[P] + A[P])/(i - P + 1)'

 if (A[i] < min_avg) { 
      P = i; 
     } 
    } 


    return min_index; 


} 

Answer 18

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<MinAvg): 
     MinAvg=Avg; 
     Index=nn;  
for nn in range(0,len(A)-2): 
    Avg=float(A[nn]+A[nn+1]+A[nn+2])/float(3); 
    if(Avg<MinAvg): 
     MinAvg=Avg; 
     Index=nn;      
return Index;  
pass 

對於解釋：

平均和上2個連續元素進行比較給出幾乎最大得分。因爲當添加一個元素時，如果平均值較小，那麼接下來的兩個元素的平均值會較小。

之後只剩下3個元素例外[ - 1，2，4，-1，2，-1]的例外。

Answer 19

這是我在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<vect.length; ++j) { 
     ++tempLength; 
     tempSum += vect[j]; 
     tempAvg = (double)tempSum/tempLength; 


     newSum = tempSum - vect[tempIndex]; 
     newIndex = tempIndex+1; 
     newAvg = newSum/(j-newIndex+1.); 

     while(newAvg < tempAvg && newIndex < j) { 
      tempIndex = newIndex; 
      tempSum = newSum; 
      tempAvg = newAvg; 
      --tempLength; 

      newSum = tempSum - vect[tempIndex]; 
      newIndex = tempIndex+1; 
      newAvg = newSum/(j-newIndex+1.); 
     } 

     if (tempAvg < minAvg) { 
      minIndex = tempIndex; 
      minAvg = tempAvg; 
     } 
     else if(tempAvg > minAvg && j-tempIndex>1) { 
      tempIndex = j; 
      tempLength = 1; 
      tempSum = vect[j]; 
     } 
    } 
    return minIndex; 
}