假设你有一个数字数组和一个查询数组:
array = [1,3,5,6,9]
queries = [5,9,3]
我们需要找到所需操作的次数，即在数组中加1或减1，使数组中的所有数字与查询数组中的元素匹配。
例如:
对于查询5，将数组的所有元素变为5所需的操作次数为abs(1-5) + abs(3-5) + abs(5-5) + abs(6-5) + abs(9-5) = 4+2+0+1+4 = 11。
对于查询9，它将是21。
对于查询3，它将是13。
是否有比O(len(array) x len(queries))更具有时间复杂度的方法?
我在python中使用的函数如下
def find_min_costs(array,queries):
for query in queries:
cost = 0
for arr in array:
cost+= abs(arr-query)
print(cost,end = ' ')
但是我的代码的时间复杂度是O(len(array) x len(queries))
我想用更好的时间复杂度来做这件事，比如O(len(array))
对输入数组进行排序(如果尚未排序)。
现在，对于每个查询q，找到查询号在数组中放置的位置pos(使用二进制搜索)。
接下来，观察到，对于左边的所有数字array[1], ..., array[pos]，它们的影响将是q - array[i]。总价为pos * q - sum_of_array_from_1_to_pos.
同样，对于右边的所有数字array[pos+1], ..., array[n]，它们的影响将是array[i] - q。总价为sum_of_array_from_pos+1_to_n - (n-pos) * q.
如果提前计算排序数组的前缀和，上述数量可以在0(1)中找到。
总的来说，准备步骤是按O(n log n)对数组进行排序，其中n为数组的长度。然后在O(n)内计算前缀和。
对于每个查询，对于二进制搜索，可以在O(log n)内完成，然后对于计算答案，可以在O(1)内完成。总数为O(m log n)，其中m为查询次数，n为数组长度。
如何使用前缀和:如果我们有前缀和p[i] = array[1] + array[2] + ... + array[i]，那么像sum_of_array_from_x_to_y这样的量就是p[y] - p[x-1]。
如何计算前缀和:p[0] = 0,p[i] = p[i - 1] + array[i].