我想计算索引 i 处的数字与 o(n) 中索引 i-1 之前的所有整数的绝对差之和。但我想不出比 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)
最佳答案
我可以提供一个 O(n log n) 的解决方案作为开始:设 fi 是结果的第 i 个数。我们有:
当从左到右遍历数组并维护元素 a0 到 ai-1的二叉搜索树时sub>,我们可以在 O(log n) 中求解公式的所有部分:
- 保持子树大小以计算大于/小于给定元素的元素
- 保留累积子树总和以回答大于/小于给定元素的总和查询
如果我们想避免实现成本,我们可以用一些更简单的数据结构替换增广搜索树:
- 事先对数组进行排序。按排序顺序为每个数字分配其排名
- 保留 binary indexed tree 0/1 值计算小于给定值的元素数量
- 保留数组值的另一个二叉索引树,以计算小于给定值的元素的总和
TBH 我不认为在一般情况下这可以在 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]
关于python - 数组中数字的绝对差之和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22943787/