数组中数字的绝对差之和

Question

我想计算一个数组中某个位置 i 的数字与它之前所有数字的绝对差的总和，并希望这个计算能在 o(n) 的时间内完成。但我想不出比 o(n^2) 更好的方法。

比如说：

[3,5,6,7,1]

这个数组中每个位置 i 的绝对差和会在另一个数组的同样位置 i 显示：

[0, 2, 4, 7, 17]

有没有人能帮我把这个计算复杂度降低到 o(n) 呢？如果不行，至少能给我一些时间复杂度更优化的建议吗？

这是我的 Python 代码：

a=[3,5,6,7,1]
n=5
absoluteSumArray=[]
for i in range(0,n):
  Sum=0
  for j in range(0,i):
     Sum+=abs(int(a[i])-int(a[j]))
  absoluteSumArray.append(Sum)

Answer 1

这里有一个关于线性决策树模型的下限，表示比较的复杂度是Omega(n log n)。这意味着不可能存在一个“好”的算法，它的运行时间低于o(n log n)（之前有两个现在已经删除的答案属于这种情况）。

这个问题可以简单地转化为计算以下内容：

f(x1, ..., xn) = sum_i sum_j |xi - xj|.

函数f在x1, ..., xn这些点上是完全可微的，当且仅当x1, ..., xn这些点彼此不同。也就是说，f完全可微的地方有n!个连通分量，而决策树的每个叶子节点最多只能处理一个这样的分量。

Answer 2

我可以提供一个O(n log n)的解决方案，首先定义一下：f_i是结果中的第i个数字。我们有：

当我们从左到右遍历数组，并维护一个包含元素 a₀ 到 a_i-1 的二叉搜索树时，我们可以在O(log n)的时间内解决公式的所有部分：

• 保持子树的大小，以便计算比某个给定数字大的或小的元素数量
• 保持子树的累积和，以便回答比某个给定数字大的或小的元素的和查询

如果我们想避免实现的复杂性，可以用一些更简单的数据结构来替代增强的搜索树：

• 提前对数组进行排序。给每个数字分配一个在排序后的顺序中的排名
• 保持一个二进制索引树，存储0/1值，以计算比某个给定值小的元素数量
• 保持另一个二进制索引树，存储数组值，以计算比某个给定值小的元素的和

说实话，我认为在一般情况下，这个问题不能在O(n)的时间内解决。至少你需要在某个时刻对数字进行排序。不过，也许数字有上限，或者你有其他限制，这样你可能能够在O(1)的时间内实现和计数操作。

一个实现示例：

# binary-indexed tree, allows point updates and prefix sum queries
class Fenwick:
  def __init__(self, n):
    self.tree = [0]*(n+1)
    self.n = n
  def update_point(self, i, val):  # O(log n)
    i += 1
    while i <= self.n:
      self.tree[i] += val
      i += i & -i
  def read_prefix(self, i):        # O(log n)
    i += 1
    sum = 0
    while i > 0:
      sum += self.tree[i]
      i -= i & -i
    return sum

def solve(a):
  rank = { v : i for i, v in enumerate(sorted(a)) }
  res = []
  counts, sums = Fenwick(len(a)), Fenwick(len(a))
  total_sum = 0
  for i, x in enumerate(a):
    r = rank[x]
    num_smaller = counts.read_prefix(r)
    sum_smaller = sums.read_prefix(r)
    res.append(total_sum - 2*sum_smaller + x * (2*num_smaller - i))
    counts.update_point(r, 1)
    sums.update_point(r, x)
    total_sum += x
  return res

print(solve([3,5,6,7,1]))  # [0, 2, 4, 7, 17]
print(solve([2,0,1]))      # [0, 2, 2]