如何找到在有序運算時間內排序數組中連續元素的算術平均值是否等於給定值？

Question

INPUT：

• 正，自然數排序後的數組，

預期的複雜性：

• 時間：O(n)
• 額外空間：O(1)

實施例：

輸入：

arr = {2,3,17,30} x=10

預期行爲：

功能打印的索引：1,2和自返回true （3 + 17）/ 2 = x = 10

輸入：

x = 30

預期行爲：

功能將打印索引3 並且由於(30)/1 = X = 30`

返回true我的算法：

我們將採用數組中第一個元素開始的算術平均值。如果x大於我們的結果，我們將把數組中的下一個元素添加到算術平均值。否則，我們將從算術平均值中減去第一個元素。

我試過了，它沒有工作。誰能幫我？

Answer 1

1. 找到最大的K，對於其中A0總和+ A1 + A2 + ...... + AK < = K *目標，
2. 如果總和== K *目標 - OK！
3. 如果總和= K *目標 - 添加下一個元素，然後減去第一個元素，直到平均值變得小於或等於目標值。

如果你的k達到數組長度，沒有解決方案。否則你有解決方案。複雜度O（n）就像第3步一樣，只添加一個數字，因爲之前的總和+ ak + 1大於k *目標，並且只能移動n次左邊界。

1. proc(array, x): 
2.  sum = 0; 
3.  left = 0; 
4.  right = 0; 
5.  do: 
6.   sum += array[right]; 
7.   right++; 
8.  while (sum+array[right] <= (right+1)*target && right<array.size); 
9.  if (sum == right*target): 
10.  for (i = left; i < right; i++): 
11.   print(array[i] + <sep>); 
12.  end_for 
13.  return; 
14. end_if 
15. while (left <= right): 
16.  if (right<array.size): sum += array[right++]; 
17.  do: 
18.   sum-=array[left++] 
19.  while (sum > target*(right-left)); 
20.  if (sum == target*(right-left)): 
21.   for (i = left; i < right; i++): 
22.    print(array[i] + <sep>); 
23.   end_for 
24.   return; 
25.  end_if 
26. end_while 
27.end_proc 

對於所有數字均爲正的數組，可以正常工作。對底片進行小幅度的修改，但是在採訪中他們經常詢問所有數字都是正數的數組。如果沒有適當的解決方案，可能需要一些額外的逃生條件。

Answer 2

如果我們計算k元素的平均值from 0 to k，我們可以告訴平均值from 1 to k或約from 0 to k + 1？ 兩個平均值1 to k和0 to k + 1是等於或大於平均第一k elemnts的。 爲什麼？ 從子集from 0 to k到子集from 1 to k，意味着刪除最小元素，因此可能不會降低總平均值。 從子集from 0 to k要子集from 0 to k + 1，意味着添加它是所有其他不小的元件，所以它可能不會降低總的平均。

我們是否知道其數量從給定數組必須是結果的一部分？是的，這是最後小於或等於目標。爲什麼？ 當它相等時，我們完成 當它不相等時，我們需要有更大和更小的元素。

然後，我們保持平均通過增加從右邊的元素，並從左側減少增加它。

public static int[] findMean(int[] input, int target) { 
    int firstGreater = 0; 
    int n = input.length; 
    while(firstGreater < n && input[firstGreater] <= target) firstGreater++; // use binary search instead! 
    if(firstGreater == 0 || firstGreater == n) return new int[]{-1,-1}; 
    int left = firstGreater - 1, right = firstGreater; 
    long sum = input[left]; 
    while ((right < n &&(right - left) * target > sum) || (left > 0 && (right - left) * target < sum)) { 
     if((right - left) * target > sum) sum += input[right++]; 
     else sum += input[--left]; 
    } 
    if((right - left) * target != sum) { 
     left = right = -1; 
    } 
    return new int[]{left, right - 1}; 
}