脸书电面不知道这个题有人见过么

题目就一道，要求后来优化时间和性能。
[hide=120]给两个数组，求所有数对的差值绝对值的总和[/120]
先是实现O（M*N）的复杂度。之后要求改进优化。
思路是先排序，然后再用二分查找第一数组里的数在第二个数组出现的位置，比第一个数组里的数小的单独计算，比第一个数组里的数大

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

-1], F(A,B) = 1+4+6 + 4+9+1 = 25

补充内容 (2018-11-11 13:48):
求大米，更新了我当时的思路给大家参考。

看到下面有同学很认真的回复，我还是把我当时的思路仔细写写吧。
1、对B数组排序（时间复杂度O(m*log(m))
2、对A数组的每个数，在排好序的B数组中进行二分查找，从二分查找的位置对数组B进行分两半（时间复杂度O(n*log(m))
3、用O(m)的空间和O(n)的时间保存B数组的和，用于快速计算
4、对步骤2中的两半分别进行求和运算，因为左边一半（一共有k个）小于A数组的当前数a，所以|a-b|=a-b，求和的时候就变成了k*a - sum(B[:k])，而右边一半（一共有m-k个）,这些数都大于或者等于当前数a，所以|a-b|=b-a，求和的时候就变成了sum(B[k:]) - (m-k-1) * a
4.1、关于求和的说明，因为在步骤3中已经保存过B的局部和了sum_b[i] = sum(B[:i])，所以左边一半的求和实际上是sum(B[:k])=sum_b[k], 而右边的一半求和是sum[k:]=sum_b[-1]-sum_b[k]。这时的时间复杂度是O(1)
4.2、面试官指出我的小BUG是上面的公式(m-k-1)我当时是写成了(m-k)
5、累计以上步骤的总和，就是最后的结果。总的时间复杂度应当是O((m+n)log(m))空间复杂度是O(m)
======
仔细回想这个题，其实已经考察了相当多的知识点，不失是一个用来面试的好题。因为最容易的O(n*m)的解法起码每个人都要会，而后面的优化可以把任何一个点做考点，一方面，如果被面的人想不出来这个解法，可以要求写一个二分查找，这个起码也是MEDIUM难度的面试题，因为这里的二分查找也不是一个标准的二分查找，因为被查找的数可能并不在数组中；另一方面，如果被面的人宣称找到了更优的解法，可以要求完成这个解法，这里最大的坑就是如果不熟悉的话可能想不起保存区部求和这个改进时间性能的做法，再一方面，如果被面的人能在三十分钟的时间内想到这个方法而且能没有BUG的写出来，的确会让人高看一线，尤其是在LEETCODE上没有原题的情况下。

看上去有戏啊。别放弃。。。

我也和楼主想的一样，就排序长的数组，计算好前缀和，然后用短的数组的元素在长数组里面查找

lz这题可以举个例子详细说一下吗？不是很理解

好像没见这题。。。。。。。

# Given 2 arrays A,B # F(A,B) # consider all pairs (a,b) such that a is in A, b is in B # F(A,B) = sum |a-b| over all such pairs (a,b) # # |a-b| #   = a-b if a>=b #   = b-a otherwise #  # A = [3, 8, -2] (of size m) # B = [4, -1] (of size n) # F(A,B) = 1+4+6 + 4+9+1 = 25

(1) 假设大数组m个数，小数组n个数， 先对小数组进行排序设为b1,b2,...,bn，这样把数轴分成了n+1个区间[-inf,b1],[b1,b2],...,[bn,+inf]

(2) 假设f(x)=|x-b1|+|x-b2|+...+|x-bn|, f(x)在每个区间都是线性函数f(x)=ax+b但是参数a,b不一样，计算出每个区间的参数a和b。（比如样例b1=-1,b2=4, 那3个区间[-inf,-1],[1,4],[4,+inf]的函数分别是-2x+3,5, 2x-3）

(3) 然后对于大数组的每个数ai，用二分查找找到位于第几个区间，然后由之前得到的参数a,b通过o(1)得到f(ai), 对f(ai)求和就是答案 （比如a2=8，位于第三个区间，f(8) = 2*8-3 =13）

时间复杂度为排序的 O(nlog n)+m个数二分查找O(m log n) = O[(m+n)log n]
空间复杂度为 O(m): 用来存参数ab

hbs198 发表于 2018-11-11 12:51
(1) 假设大数组m个数，小数组n个数， 先对小数组进行排序设为b1,b2,...,bn，这样把数轴分成了n+1个区间[-in ...

谢谢分析。其实当时面试官已经很友好地把公式|a-b|定义单独写出来了。|a-b|==(a-b) if a>=b, else (b-a)。他这样写出来对分析和思考很有帮助。

A = [3,8,2], B = [4, -1], F(A,B) = 1+4+6 + 4+9+1 = 25. 这个例子是不是给错了 绝对值之和