# -Smallest difference

###### tags: `Medium`

Q: 從兩個不一定等長的數組中找相減最小的一對數出來。

想法：先排序，再從頭互相比對，如果比對方小就拿更大的出來比，直到比完

比對過程 O(m+n)
由於用了排序，故為 O(mlog(m)+nlog(n)) 上方m+n可忽略

vector<int> smallestDifference(vector<int> arrayOne, vector<int> arrayTwo) {
  // Write your code here.
  sort(arrayOne.begin(), arrayOne.end());
  sort(arrayTwo.begin(), arrayTwo.end());
  int smallestNum = INT_MAX;
  vector<int> smallestPair;
  int oneIdx = 0;
  int twoIdx = 0;
  while (oneIdx < arrayOne.size() && twoIdx < arrayTwo.size()){
      if (abs(arrayOne[oneIdx] - arrayTwo[twoIdx]) < smallestNum){
          smallestNum = abs(arrayOne[oneIdx] - arrayTwo[twoIdx]);
          smallestPair = {arrayOne[oneIdx], arrayTwo[twoIdx]};
      }
      if (arrayOne[oneIdx] > arrayTwo[twoIdx])
          twoIdx++;
      else if (arrayOne[oneIdx] < arrayTwo[twoIdx])
          oneIdx++;
      else
          return vector<int>{arrayOne[oneIdx], arrayTwo[twoIdx]};
  }
  return smallestPair;
}