在排序数组之和中，以一个值为界的因素数最大化

Question

我有一个大小为n的整数排序数组，这些值不是唯一的。我需要做的是:给定一个B，我需要找到一个i<A[n]，使得|A[j:1 to n]-i|的和小于B，并且这个特别的和贡献了Ajs的最大数量。我有一些想法，但我似乎找不到更好的从天真的n*B和n*n算法。对O(nlogn)或O(n)有什么想法吗？例如:想象一下

A=1，2，10，10，12，14和B<7，那么最好的I是12，因为我有4个Ajs贡献了我的总和。10和11也同样好，因为如果i=10我得到10 - 10 + 10 - 10 +12-10 + 14-10 = 6<7

Answer 1

我认为你可以在O(n)中使用以下三种技巧：

累积和

预先计算存储和(A0:K)的数组Ck。

这可以通过时间O(n)中的Ck=Ck-1+Ak递归地完成。这个数组的好处是您可以通过Cb 1计算和(Aa:B)。

最佳中点

因为您的元素是排序的，那么就很容易计算出最佳i来最小化绝对值之和。事实上，最好的我将永远由中间的条目。如果列表的长度是偶数，那么两个中心元素之间的所有i值都会给出最小绝对值。

例如，对于列表10、10、12、14，中心元素是10和12，所以I在10到12之间的任何值都会最小化和。

迭代搜索

现在您可以对元素进行一次扫描，以找到最佳值。

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

跟踪电子见的最大值，它的分数

这个循环最多可以旋转2n次，所以它是O(n)。

As:e的分数是由sum _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]

我们可以用预计算数组Ck来计算表达式中的和。

编辑

如果端点必须始终为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

Answer 2

O(n)中的一个解:从结尾开始计算an-an-1 :设d=14-12 => d=2和r= by => r=5，然后重复操作，但将d乘以2: d=12-10 => d=2和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

Answer 3

对于一种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也能做到这一点。我们必须以一种聪明的方式使用bin搜索来在每次迭代中找到左索引和右索引，以便在每次迭代中可能的结果范围变得更小。这可以很容易做到，但我们必须处理重复，因为他们可以破坏我们的垃圾箱搜索减少。