5

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

有任何想法吗？谢谢！

4

3 回答 3

8

您可以通过首先根据 B 中的值对两个数组进行排序，然后执行单次扫描，在 O(nlogn) 时间内完成此操作。

数组排序后，如果 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 值。

于 2013-01-07T19:49:33.353 回答
5

我相信我能做到这一点是 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
  • C k [i] = B[i] - B[k]，对于 k < i < n

让我们再定义两件事。

定义： T k = Σ A[i] for 0 <= i < k

定义： U k = Σ A[i] for k < i < n

（也就是说，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] 加到 C 中从 0 到 k 的每个元素上，然后从 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 的总和

它们之间的差异是 (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 0、T 0和 U 0，并且我们可以在恒定时间内从 S k到 S k+1 ，所以我们可以在线性时间内计算所有的 S k。所以这样做，记住最小的，你就完成了。

使用排序排列的逆来获取k原始数组的 。

于 2013-01-07T19:51:50.680 回答
3

这是 O(NlogN) 解决方案。例子

A 6 2 5 10 3 8 7
B 1 5 4 3  6 9 7

1）首先将两个数组排序为B的顺序增加。A的元素只是与B绑定。排序后，我们得到

 A  6 10 5 2 3 7
 B  1 3  4 5 6 7

由于B现在井井有条。我们有

n-1
sum A[i]|B[i]-B[k]| 
i=0

 k-1                 n-1
=sum A[i](B[k]-B[i])+ sum A[i](B[k]-B[i])
 i=0                 i=k+1
      k-1       n-1          k-1           n-1
=B[k](sum A[i] -sum A[i]) - (sum A[i]B[i]- sum A[i]B[i])
      i=0      i=k+1        i=0           i=k+1

2) 我们计算数组 A 的前缀和 sumA=0 6 16 21 23 26 33

          i=e
With sumA sum A[i] can be calcuated in O(1) time for any s and e. 
          i=s

出于同样的原因，我们可以计算 A[i]B[i] 的前缀和。所以对于每个 k，要检查它的值，只需要 O(1) 时间。所以总时间复杂度是O(NlogN)+O(N).

于 2013-01-07T20:15:27.560 回答