给定两个数组找到最小化和A [i]*| B [i] -B [k] |的索引k

Question

我给了两个包含自然数A和B的数组,我需要找到最小化和A [i]*| B [i] -B [k] |的索引k.从i = 0到n-1.(两个数组都有相同的长度)它在O(n ^ 2)中显然很容易,我只计算0和n-1之间所有k的所有和,但我需要更好的运行时复杂度.

有任何想法吗？谢谢!

Answer 1

您可以在时间O(nlogn)中执行此操作,方法是首先根据B中的值对两个数组进行排序,然后执行单次扫描.

一旦数组被排序,那么如果i> k则B [i]> = B [k]而如果i <= k则B [i] <= B [k],因此总和可以重写为:

sum A[i] * abs(B[i]-B[k]) = sum A[i]*(B[i]-B[k])  for i=k..n-1
                            + sum A[i]*(B[k]-B[i])  for i=0..k-1

    = sum A[i]*B[i] for i=k..n-1
      - B[k] * sum A[i] for i=k..n-1
      + B[k] * sum A[i] for i = 0..k-1
      - sum A[i]*B[i] for i = 0..k-1

您可以预先计算时间O(n)中的所有总和,然后让您评估O(n)中每个位置的目标总和,并选择给出最佳分数的k值.

Answer 2

我相信我能做到的就是O(n log n).

首先,对B数组进行排序,对数组应用相同的排列A(并记住排列).这是O(n log n)部分.由于我们对所有i进行求和,因此对A和B数组应用相同的置换不会改变最小值.

对于排序B数组,算法的其余部分实际上是O(n).

对于每个k,定义一个数组C _k [i] = | B [i] - B [k] |

(注意:我们实际上不会构造C _k ......我们只是将它用作概念以便于推理.)

观察到我们试图最小化的量(超过k)是A [i]*C _k [i] 的总和.让我们继续吧,给它一个名字:

定义:S _k =ΣA[i]*C _k [i]

现在,对于任何特定的k,C _k是什么样的？

那么,C _k [k] = 0,显然.

更有趣的是,由于B数组已经排序,我们可以摆脱绝对值符号:

• C _k [i] = B [k] -B [i],0 <= i <k
• C _k [i] = 0,i = k
• 对于k <i <n,C _k [i] = B [i] -B [k]

让我们再定义两件事.

定义:T _k =ΣA[i] 0 <= i <k

定义:对于k <i <n,U _k =ΣA[i]

(即,T _k是A的第一个k-1个元素的总和.U _k是除了A 的前k个元素之外的所有元素的总和.)

关键观察:给定S _k,T _k和U _k,我们可以在恒定时间内计算S _{k + 1},T _{k + 1}和U _{k + 1}.怎么样？

T和U很容易.

问题是,我们如何从S _k到S _{k + 1}？

考虑当我们去C _{k + 1}时C _k会发生什么.我们简单地将B [k + 1] -B [k]添加到从0到k的C的每个元素,并且我们从C的每个元素中减去相同的量,从k + 1到n(证明这一点).这意味着我们只需要添加T _k*(B [k + 1] - B [k])并减去U _k*(B [k + 1] - B [k])以从S _k到S _{k + 1}.

代数地...... S _k的前k个项只是A [i]*(B [k] - B [i])的0到k-1之和.

S _{k + 1}的前k项是A [i]*(B [k + 1] - B [i])从0到k-1的和

它们之间的差异是从0到k-1的和(A [i]*(B [k + 1] - B [i]) - (A [i]*(B [k] - B [ i])).分解A [i]项并取消B [i]项,得到A [i]*(B [k + 1] - B [k])从0到k-1之和,这只是T _k*(B [k + 1] - B [k]).

类似地,对于S _k的最后nk-1项.

由于我们可以在线性时间内计算S ₀,T ₀和U ₀,并且我们可以在恒定时间内从S _k到S _{k + 1},我们可以在线性时间内计算所有S _k.所以,记住最小的,你就完成了.

使用排序排列的倒数来获取k原始数组.