2

サイズ n の整数のソート済み配列があります。これらの値は一意ではありません。私がする必要があるのは: B が与えられた場合、i<A[n]の合計が|A[j:1 to n]-i|B よりも小さく、その特定の合計に最大数の A[j] が寄与するような を見つける必要があります。私にはいくつかのアイデアがありますが、素朴な n*B および n*n アルゴリズムからより良いものを見つけることができないようです。O(nlogn) または O(n) に関するアイデアはありますか? 例: 想像してみてください。

A[n] = 1 2 10 10 12 14 および B<7 の場合、最高の i は 12 です。なぜなら、4 つの A[j] が合計に寄与するからです。10 と 11 も同様に良いです i=10 の場合、私は 10 - 10 + 10 - 10 +12-10 + 14-10 = 6<7 を得ました

4

3 に答える 3

1

O(n) の解: 最後から始めて a[n]-a[n-1] を計算します: d=14-12 => d=2 および r=Bd => r=5 として、 d=12-10 => d=2 and r=r-2*d => r=1, r=1 合計が B 未満でなければならないため、アルゴリズムの終わり:

インデックスが 0..n-1 の配列を使用

i=1
r=B
while(r>0 && n-i>1) {
  d=a[n-i]-a[n-i-1];
  r-=i*d;
  i++;
}
return a[n-i+1];

絵の方がわかりやすいかも

14       x
13       x  -> 2
12      xx
11      xx  -> 2*2
10    xxxx    -> 3*0
 9    xxxx   
 8    xxxx
 7    xxxx
 6    xxxx
 5    xxxx
 4   xxxxx
 3   xxxxx
 2  xxxxxx
 1 xxxxxxx
于 2012-11-13T13:22:26.570 に答える
0

次の3つのトリックを使用して、O（n）でそれを実行できると思います。

累積合計

sum（A [0：k]）を格納する配列C[k]を事前計算します。
これは、時間O（n）でC [k] = C [k-1] +A[k]を介して再帰的に実行できます。この配列の利点は、C [b] -C [a-1]を介してsum（A [a：b]）を計算できることです。

最高の中点

要素がソートされているため、絶対値の合計を最小化するための最良のiを簡単に計算できます。実際、最高のiは常に真ん中のエントリによって与えられます。リストの長さが偶数の場合、2つの中央要素間のiのすべての値は、常に最小の絶対値を示します。

たとえば、リスト10、10、12、14の場合、中心要素は10と12であるため、iの値が10から12の間であれば、合計が最小になります。

反復検索

これで、要素を1回スキャンして、最適な値を見つけることができます。

1. Init s=0,e=0
2. if the score for A[s:e] is less than B increase e by 1
3. else increase s by 1
4. if e<n return to step 2

スコアがB未満である、見られたesの最大値を追跡します。これがあなたの答えです。

このループは最大で2n回回ることができるため、O（n）になります。

A [s：e]のスコアは、合計| A [s：e] -A [（s + e）/2]|で与えられます。

m =（s + e）/2とします。

score = sum |A[s:e]-A[(s+e)/2]| 
= sum |A[s:e]-A[m]|
= sum (A[m]-A[s:m]) + sum (A[m+1:e]-A[m])
= (m-s+1)*A[m]-sum(A[s:m]) + sum(A[m+1:e])-(e-m)*A[m]

事前に計算された配列C[k]を使用して、この式の合計を計算できます。

編集

エンドポイントが常にnでなければならない場合は、次の代替アルゴリズムを使用できます。

1. Init s=0,e=n
2. while the score for A[s:e] is greater than B, increase s by 1

Pythonコード

アルゴリズムのPython実装は次のとおりです。

def fast(A,B):
    C=[]
    t=0
    for a in A:
        t+=a
        C.append(t)

    def fastsum(s,e):
        if s==0:
            return C[e]
        else:
            return C[e]-C[s-1]

    def fastscore(s,e):
        m=(s+e)//2
        return (m-s+1)*A[m]-fastsum(s,m)+fastsum(m+1,e)-(e-m)*A[m]

    s=0
    e=0
    best=-1
    while e<len(A):
        if fastscore(s,e)<B:
            best=max(best,e-s+1)
            e+=1
        elif s==e:
            e+=1
        else:
            s+=1
    return best

print fast([1,2,10,10,12,14],7)
# this returns 4, as the 4 elements 10,10,12,14 can be chosen
于 2012-11-13T13:48:50.113 に答える
0

アプローチのためにこの方法を試してくださいO(N) with N size of array：

minpos = position of closest value to B in array (binary search, O(log(N))
min = array[minpos]

if (min >= B) EXIT, no solution

// now, we just add the smallest elements from the left or the right
// until we are greater than B

leftindex = minpos - 1
rightindex = minpos + 1

while we have a valid leftindex or valid rightindex:
    add = min(abs(array[leftindex (if valid)]-B), abs(array[rightindex (if valid)]-B))
    if (min + add >= B)
        break
    min += add
    decrease leftindex or increase rightindex according to the usage

min is now our sum, rightindex the requested i (leftindex the start)

(一部のインデックスが正しくない可能性があります。これは単なるアイデアであり、実装ではありません)

小さい b の平均的なケースはO(log(N)). 線形の場合は、配列全体を使用できる場合にのみ発生します。

よくわかりませんが、おそらくこれも で実行できますO(log(N)*k) with N size of array and k < N。可能な結果範囲が反復ごとに小さくなるように、ビン検索を巧妙な方法で使用して、すべての反復で leftindex と rightindex を見つける必要があります。これは簡単に実行できますが、ビン検索の削減を破壊する可能性があるため、重複に注意する必要があります。

于 2012-11-13T21:39:32.127 に答える