LintCode 387: Smallest Difference

題目描述

給定兩個整數(shù)數(shù)組（第一個是數(shù)組A，第二個是數(shù)組B），在數(shù)組A中取A[i]，數(shù)組B中取B[j]，A[i]和B[j]兩者的差越小越好(|A[i] - B[j]|)。返回最小差。

樣例

給定數(shù)組A = [3,4,6,7]，B = [2,3,8,9]，返回 0。

Mon Feb 27 2017

思路

先將兩個數(shù)組排序，然后分別用一個指針i, j，從前往后遍歷，若A[i] > B[j]，要想差更小，那么需要j++，其它情況同理。

時間復(fù)雜度是 \(O(nlogn)\)，主要是需要排序。

本題還有其它的方法，遍歷A數(shù)組，然后用二分查找B數(shù)組，也值得一試。

代碼

// 最小差 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; }

轉(zhuǎn)載于:https://www.cnblogs.com/genkun/p/6474604.html

總結(jié)

以上是生活随笔為你收集整理的LintCode 387: Smallest Difference的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。