数字数组全部相等的最少运算次数

Question

您有一组数字，例如

[2, 5, 1]

。您有第二个数字数组，例如

[8, 4, 3]

。对于第二个数组中的每个数字，需要多少次操作才能使第一个数组全部等于该数字？一次只能递增或递减 1。

To get to 8, it would take (8-2)+(8-5)+(8-1)=16 operations. 
To get to 4, it would take (4-2)+(5-4)+(4-1)=6 operations. 
To get to 3, it would take (3-2)+(5-3)+(3-1)=5 operations. 
So the answer would be [16, 6, 5].

我能够用一行完成此操作：

answer = [sum(abs(x-y) for x in a1) for y in a2]

但是当数组最多可以有 10⁵ 项时，这还不够快。我怎样才能更快地做到这一点？

Answer 1

嗯，我有一个解决方案。首先，对第一个数组进行排序，因为这里第一个数组的值的位置并不重要。

其次，计算排序数组的前缀和。

第三，对于第二个数组的每个值，对第一个排序数组进行二分查找。并找到 Value 的下限。然后根据前缀和可以计算出该值之前需要增加多少以及该值之后可以减少多少。

总体时间复杂度将为 o(n*log(n)) 。 希望能过去。