将编程效率从 O(n^2) 提高到 O(n)

Question

假设您有一个数字数组和一个查询数组：

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))

Answer 1

对输入数组进行排序（如果尚未排序）。

现在，对于每个查询，找到查询编号在数组中放置的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.

如果预先计算排序数组的前缀和，则上述数量的复杂度为 O(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].