3

入力：

  • 正の自然数のソートされた配列、

予想される複雑さ:

  • 時間：O(n)
  • 追加スペース:O(1)

例：

入力：

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

予想される行動：

関数はインデックス : 1,2 を出力し、(3+17)/2 = x = 10 なので true を返します。

入力：

x = 30

予想される行動：

(30)/1= x = 30であるため、関数はインデックス 3 を出力し、true を返します。

アルゴリズムへの私のアプローチ:

配列の最初の要素から始まる算術平均をとります。x が結果よりも大きい場合は、配列の次の要素を算術平均に追加します。そうでない場合は、算術平均から最初の要素を減算します。

試してみましたが、うまくいきませんでした。誰でも私を助けることができますか？

4

2 に答える 2

1
  1. a0+a1+a2+...+ak <= k*target の合計である最大の k を見つけます
  2. 合計 == k*ターゲットの場合 - OK
  3. 合計 != k*ターゲットの場合 - 次の要素を追加し、平均がターゲット以下になるまで最初の要素を減算します。

k が配列の長さに達した場合、解決策はありません。それ以外の場合は、解決策があります。複雑さ O(n) まるでステップ 3 のように、前の合計 + ak+1 が k*target よりも大きく、左の境界線を n 回しか移動できないため、1 つの数値のみを追加します。

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

すべての数値が正の配列に対して適切に機能します。ネガには小さな変更が必要ですが、インタビューでは、すべての数値が正の配列についてよく尋ねられます。適切な解決策がない場合は、いくつかの追加のエスケープ条件が必要になる場合があります。

于 2016-08-24T14:53:03.563 に答える
0

k要素の平均を計算した場合、平均について、またはについてfrom 0 to k何がわかりますか? 平均との両方が、最初の要素の平均以上です。なんで？サブセットからサブセットに移動することは、最小の要素を削除することを意味するため、合計平均が減少しない場合があります。サブセットからサブセットに移動すると、他の要素よりも小さくない要素を追加することを意味するため、合計平均が減少しない場合があります。from 1 to kfrom 0 to k + 11 to k0 to k + 1kfrom 0 to kfrom 1 to kfrom 0 to kfrom 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};
}
于 2016-08-24T22:28:05.827 に答える