LeetCode 面试题 16.06.最小差

给定两个整数数组a和b，计算具有最小差绝对值的一对数值（每个数组中取一个值），并返回该对数值的差

示例：

输入：{1, 3, 15, 11, 2}, {23, 127, 235, 19, 8}
输出：3，即数值对(11, 8)

提示：

1 <= a.length, b.length <= 100000
-2147483648 <= a[i], b[i] <= 2147483647
正确结果在区间 [0, 2147483647] 内

先对数组a、b进行排序，然后双序列双指针，每次计算两指针指向数字的最小差，然后右移指向较小数字的指针：

class Solution {
public:int smallestDifference(vector<int>& a, vector<int>& b) {sort(a.begin(), a.end());sort(b.begin(), b.end());int aIdx = 0;int bIdx = 0;long long ans = numeric_limits<int>::max();while (aIdx < a.size() && bIdx < b.size()) {ans = min(ans, abs((long long)a[aIdx] - b[bIdx]));if (a[aIdx] < b[bIdx]) {++aIdx;} else {++bIdx;}}return ans;}
};

如果a的长度为n，b的长度为m，则此算法时间复杂度为O(nlogn + mlogm)，空间复杂度为O(logn + logm)。