[演算法題目] Smallest Difference

本題資訊

難度：medium
使用語言：C++
相關概念：Arrays

題目敘述

Given two arrays of integers, compute the pair of values (one value in each array) with the smallest (non-negative) difference. Return an array containing these two numbers.

Input:
arrayOne = [1, 3, 15, 11, 2]
arrayTwo = [23, 127, 235, 19, 8]

Output:
[11, 8]

這題 input 有兩個 array，各挑出一個數字，希望找出相減後絕對值最小的組合。

Idea

暴力解一樣可以解決這個問題，把所有的組合全算出來，並且直接找出最小值，只要不在意時間複雜度是 \(O(n^2)\) 這題就結束了。

這題蠻特別是 input 有兩個 array，按照之前慣例，在 array 有關的問題中有要做大小處理的狀況，我會想先排序。

首先要設定 current 和 smallest 兩個變數，分別存放目前的差值以及目前累積到的最小差值。

陣列中兩個數相減，若等於零當然就是直接回傳這個 pair，毫無懸念。其它狀況則是會有其中一個數字比較大，為了維持相減之後仍是正數，這裡需要做第一次的條件判斷比大小，並將差值存在 current 變數中。另外還要讓 index 繼續往後走，希望能夠越減越靠近 0，所以減數所位於的那一個陣列的 index 要前進（變大一些）。再來就是更新 smallest 了，後續才可以進行比對，並且儲存目前差值最小的 pair。

#include <vector>
using namespace std;

vector<int> smallestDifference(vector<int> arrayOne, vector<int> arrayTwo) {
  sort(arrayOne.begin(), arrayOne.end());
  sort(arrayTwo.begin(), arrayTwo.end());
  
  int smallest = INT_MAX;
  int current;
  int index1 = 0, index2 = 0;
  vector<int> smallestPair;
  
  while(index1 < arrayOne.size() && index2 < arrayTwo.size()){
    int num1 = arrayOne[index1];
    int num2 = arrayTwo[index2];
    
    if (num1 < num2){
        current = num2 - num1;
        index1++;
    } else if (num2 < num1){
        current = num1 - num2;
        index2++;
    } else {
        return vector<int>{num1, num2};
    }
    if (smallest > current){
        smallest = current;
        smallestPair = {num1, num2};
    }
  }
  return smallestPair;
}

時間複雜度：\(O(n\log n + m\log m)\)，\(n\) 和 \(m\) 分別指兩個 array 的元素個數。
空間複雜度：\(O(1)\)

在這一題學到 INT_MAX 比較實際的用法，變數 current 我本來就沒有設定初始的值，不怎麼影響，但 smallest 變數因為要不斷更新為最小，在邏輯上會希望能夠設定初始值為最大值。雖然讀基礎概念的時候一定有讀過這部分，但實際應用還真的是熊熊記不起來。