c++ - 数字与数字数组的差之和

这是我的问题。给定一个整数数组和另一个整数 k，求数组中每个元素与 k 的差之和。

例如，如果数组是 2, 4, 6, 8, 10 并且 k 是 3

Sum of difference
= abs(2 - 3) + abs(4-3) + abs(6 - 3) + abs(8 - 3) + abs(10 - 3)
= 1 + 1 + 3 + 5 + 7
= 17

数组始终保持不变，最多可包含 100000 个元素，将有 100000 个不同的 k 值需要测试。 k 可能是也可能不是数组的元素。这必须在 1s 或大约 100M 操作内完成。我如何实现这一目标？

最佳答案

如果您添加一个花费 O(N * log N) 的预处理步骤，您可以在 O(log N) 中运行多个绝对差之和的查询。

对数组进行排序，然后为数组中的每一项存储小于或等于对应项的所有数字的总和。这可以在 O(N * log N) 中完成现在您有一对数组，如下所示:

2   4   6   8  10 // <<== Original data
2   6  12  20  30 // <<== Partial sums

此外，存储数组中所有数字的总T。

现在您可以通过对原始数组运行二分搜索并使用部分和数组中的和来计算答案来获得绝对差的和:减去目标左侧所有数字的和 k从目标次数左边的数字计数k，然后从数字右边的总和中减去计数次数k，并且将两个数字相加。可以通过从总 T 中减去左侧的部分和来计算数字右侧的部分和。

对于k=3，二分查找让您定位到1。

关于c++ - 数字与数字数组的差之和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24697820/