数组中两个数字之间的最小绝对差值

Question

给定两个数组A和B,我想从A中找到一个数字,从B中找到一个数字,这样两个数字之间的绝对差值就越小.

例如

A = 1 2 9
B=  4 5  6

Ans:2,4作为Math.abs(2-4)= 2

Answer 1

对两个数组进行排序,然后并行迭代:对于每个项目A,B通过线性搜索搜索最近的项目.在B上一个项目停止的位置开始线性搜索A.永远记住到目前为止发现的最小距离.

的时间复杂度是用于排序和O(M + N)为最后的搜索,其中m和n是各自的长度O(米日志M + N log n)的A和B.

Answer 2

它可以在O(nlogm + mlogm)= O(nlogm)中完成:(
m是最小的数组长度)
假设B是较小的数组

sort array B
minimum =  | A[0]-B[0] | 
for each a in A:
binary search for a in B - return the closest numbers let the numbers be b1,b2 (*)
if min{|b1-a|,|b2-a|} is smaller then the previous minimum - store it as the new minimum

(*)二进制搜索在您最接近该号码时停止(或者如果存在则找到它)
首先检查哪个较小(A或B)将确保更好的性能.-