1200. 最小絕對差

思路

要找到絕對值差最小的元素對，並按照升序的順序返回。

「絕對值差最小」相當於座標軸上的距離最小，每一個數都可以看作在軸上的點。
因此排序過後遍歷，就相當於在座標軸上從最小的點往後面走，第一個遇到的的點就是離自己最近的。

假如遇到距離比現在更小的，就丟掉紀錄到一半的結果，重新開始紀錄。

程式碼

排序

class Solution {
public:
    vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
        ranges::sort(arr);
        int n = arr.size();
        int mnDiff = INT_MAX;
        vector<vector<int>> res;
        for(int i = 1; i < n; ++i) {
            int diff = arr[i] - arr[i - 1]; // arr 嚴格遞增
            if(diff < mnDiff) {
                mnDiff = diff;
                res.clear();
                res.push_back({arr[i - 1], arr[i]});
            }
            else if(diff == mnDiff) {
                res.push_back({arr[i - 1], arr[i]});
            }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n\log{n})$，主要在排序上。
• 空間複雜度：$O(n)$，最糟的情況是一共有 $n-1$ 對答案。