Lintcode387 The Smallest Difference solution 题解
发布在刷题能手——Lintcode 题解2018年3月31日view:281
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

Given two array of integers(the first array is array A, the second array is array B), now we are going to find a element in array A which is A[i], and another element in array B which is B[j], so that the difference between A[i] and B[j] (|A[i] - B[j]|) is as small as possible, return their smallest difference.

给定两个整数数组(第一个是数组A,第二个是数组B),在数组 A 中取 A[i],数组 B 中取 B[j],A[i] 和 B[j]两者的差越小越好(|A[i] - B[j]|)。返回最小差。

【题目链接】

www.lintcode.com/en/problem/the-smallest-difference/

【题目解析】

题目的要求是O(nlogn)的时间复杂度,那么就会想到two pointers的做法:

  1. 首先,two pointers做法一般都用在有序数组上,所以上来先把A和B排序;

  2. 然后,将A中的element A[i]一个一个拿出来,跟B里的比较。这里不需要将B中的每一个element都拿来比较,其实最需要比的只是与A[i]相近的那些。由此我们可以利用有序数组的特点,做一个二分搜索,挑最重要的那些来比。比如,如果A[i]比B[mid]大,那么diff有可能更小的就只能在B[mid]之后的那些数。

【参考答案】

www.jiuzhang.com/solutions/the-smallest-difference/

评论
发表评论
暂无评论
WRITTEN BY
PUBLISHED IN
刷题能手——Lintcode 题解

日常更新算法刷题~

我的收藏