LeetCode 面试题 16.06. 最小差[1]
给定两个整数数组 a
和 b
,计算具有最小差绝对值的一对数值(每个数组中取一个值),并返回该对数值的差。
说明:
1 <= a.length, b.length <= 100000
-2147483648 <= a[i], b[i] <= 2147483647
[-2147483648, 2147483647]
内示例1
输入:{1, 3, 15, 11, 2}, {23, 127, 235, 19, 8}输出:3,即数值对(11, 8)
首先最暴力的方法就是 暴力枚举两个数组中的所有数对,然后计算绝对值最小的差值,这样显然是会超时的。
所以我们先分别对两个数组从小到大进行排序,然后用双指针的方法来计算。
是不是有点类似归并排序的合并数组过程?但是这里有个区别,最后遍历完之后,一定会有某个数组还没遍历完。而那些没遍历的数字其实都大于另一个数组中最大的数,所以没有必要再和另一个数组最大值做差值了。这样差值只会越来越大,没有意义。
最终的时间复杂度就是 。
class Solution {public: int smallestDifference(vector<int>& a, vector<int>& b) { sort(a.begin(), a.end()); sort(b.begin(), b.end()); int n = a.size(), m = b.size(); int i = 0, j = 0; long res = INT_MAX; while (i < n && j < m) { res = min(res, abs(long(a[i])-long(b[j]))); if (a[i] > b[j]) ++j; else ++i; } return res; }};
class Solution: def smallestDifference(self, a: List[int], b: List[int]) -> int: a.sort() b.sort() n, m = len(a), len(b) i, j, res = 0, 0, 2147483647 while i < n and j < m: res = min(res, abs(a[i]-b[j])) if a[i] > b[j]: j += 1 else: i += 1 return res
[1]
LeetCode 面试题 16.06. 最小差: https://leetcode-cn.com/problems/smallest-difference-lcci/