LintCode 387: Smallest Difference
題目描述
給定兩個整數數組（第一個是數組A，第二個是數組B），在數組A中取A[i]，數組B中取B[j]，A[i]和B[j]兩者的差越小越好(|A[i] - B[j]|)。返回最小差。
樣例
給定數組A = [3,4,6,7]，B = [2,3,8,9]，返回 0。
Mon Feb 27 2017
思路
先將兩個數組排序，然后分別用一個指針i, j，從前往后遍歷，若A[i] > B[j]，要想差更小，那么需要j++，其它情況同理。
時間復雜度是 \(O(nlogn)\)，主要是需要排序。
本題還有其它的方法，遍歷A數組，然后用二分查找B數組，也值得一試。
代碼
// 最小差
int smallestDifference(vector<int> &A, vector<int> &B)
{sort(A.begin(), A.end());sort(B.begin(), B.end());int i = 0, j = 0, min = INT_MAX;while(i < A.size() && j < B.size()){int diff;if (A[i] > B[j]){diff = A[i] - B[j];++j;}else if (A[i] < B[j]){diff = B[j] - A[i];++i;}else return 0;if (diff < min) min = diff;}return min;
}
)
