给定两个整数数组（第一个是数组 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。

 

时间复杂度 O(n log n)

 

没有说明原数组是有序的，我们可以先给两个数组排个序，nLogn

最简单的数组不重叠的情况两种，先排除

重叠的话，遍历A，卡住每个A[i]作为target去B[]里面找最接近的，可以使用二分法

1 int smallestDifference(vector
      
        &A, vector
       
         &B) { 2         // write your code here 3         if(A.size()<=0 || B.size()<=0){ 4             return 0; 5         } 6         sort(A.begin(), A.end()); 7         sort(B.begin(), B.end()); 8          9         if(A[A.size()-1] <= B[0]){10             return abs(B[0]-A[A.size()-1]);11         }12         else if(B[B.size()-1] <= A[0]){13             return abs(A[0]-B[B.size()-1]);14         }15         else{16             int result=INT_MAX;17             int low, mid, high;18             for(int i=0;i
        
         B[mid]){27                         low=mid+1;28                     }29                     else if(A[i]
         
           0) {35                     result = min(result, abs(A[i] - B[mid - 1]));36                 }37                 if (mid < B.size() - 1) {38                     result = min(result, abs(A[i] - B[mid + 1]));39                 }40             }41             return result;42         }43         44     }
         
        
       
      

注意二分法mid不可能取到数组的第一个或者最后一个，所以需要额外代码判断下。