[面试]计算两个数组元素差值的最大值?

By | 2017年12月26日

几个月前去某公司面试,面试官问了一个算法题:给定两个整型数组A和B,如何计算两个数组元素之差的最大值?当时估计一紧张就不知道怎么想的,连什么动态规划都出来了。现在想想其实是一个很简单的问题,根本用不到什么动态规划。

思路:

两个数组元素的差,其实对应到数轴上的两点之间的距离,既然这两个点来自两个数组,其实只要其中一个最大,另一个最小,那么这样的两点之间的距离肯定就是最大的。

方法:

一次遍历数组A:找到A的最大值Amax和A的最小值Amin

一次遍历数组B:找到B的最大值Bmax和B的最小值Bmin

计算两个“距离”:

ABS(Amax-Bmin)和ABS(Bmax-Amin)

最大距离必是这两个值中的其中一个,比较一下即可。

发表评论

电子邮件地址不会被公开。 必填项已用*标注