数字与数组之差的总和

Question

这是我的问题.给定一个整数数组和另一个整数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个元素,并且将测试100个不同的k值.k可以是也可以不是数组的元素.这必须在1s或大约100M的操作中完成.我该如何实现这一目标？

Answer 1

O(log N)如果添加成本预处理步骤,则可以对绝对差值的总和运行多个查询O(N * 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.

• 左边的部分和是2
• 左边的项目数是1
• 右边的部分和是(30-2)= 28
• 右边的项目数是4
• 你计算(1*3-2)+(28-4*3)= 1 + 16 = 17

Answer 2

首先对数组进行排序,然后计算一个数组,该数组存储生成的排序数组的前缀之和.让我们表示这个数组p,你可以计算p线性时间p[i] = a[0] + a[1] + ... a[i].现在有这个数组可以用恒定的复杂性回答的问题是什么元素之和a[x] + a[x+1] + .... +a[y](即指数x来y).要做到这一点,你只需计算p[y] - p[x-1](当x为1时要特别小心).

现在回答类型的查询是什么是绝对差值之和k,我们将问题分为两部分 - 大于k的数字和小于k的数字的总和是多少.为了计算这些,执行二分搜索以找到排序中的k的位置a(表示该位置idx),并计算a之前idx(表示s)和之后idx(表示S)的值的总和.现在绝对差异的总和k是idx * k - s + S - (a.length - idx)* k.这当然是伪代码,我的意思是a.length是元素的数量a.

执行线性预计算后,您将能够回答查询O(log(n)).请注意,如果您计划执行多个查询,此方法才有意义.如果您只打算执行单个查询,则可能不会更快O(n).