1200. Minimum Absolute Difference

📘 題目敘述

給定一個整數陣列 arr，請找出所有兩兩元素之間差值的最小絕對值。

你需要回傳一個二維陣列，包含所有滿足以下條件的數對 [a, b]：

• |a - b| 等於整個陣列中最小的絕對差值
• 回傳的每一組數對必須依照遞增順序（a < b）
• 所有數對本身也必須按照遞增順序排列

條件限制

• 2 ≤ arr.length ≤ 10^5
• -10^6 ≤ arr[i] ≤ 10^6

🧠 解題思路

我的核心想法是：如果陣列已經排序過，那「最小絕對差值」一定只會出現在「相鄰的元素之間」。

• 排序後，距離最接近的兩個數，一定會排在一起
• 不需要去檢查所有 O(n^2) 的組合，只要看相鄰元素即可

因此我把整題拆成兩個階段來做：

1. 先排序
2. 分兩次掃描：第一次找出最小差值，第二次收集所有符合該差值的數對

所有變數

• arr：輸入的整數陣列（會先排序）
• diff：目前找到的最小相鄰差值
• ans：最後要回傳的答案，存所有 [arr[i], arr[i + 1]]
• i：掃描排序後陣列時使用的索引

🪜 主要流程步驟

第一步：排序陣列

• 先對 arr 進行排序
• 排序後，相鄰元素的差值就代表可能的最小絕對差

第二步：找出最小差值

• 從左到右掃描排序後的陣列
• 每次計算 arr[i + 1] - arr[i]
• 若差值比目前 diff 小，就更新 diff

第三步：收集所有符合最小差值的數對

• 再次掃描排序後的陣列
• 如果相鄰元素差值等於 diff，就把 [arr[i], arr[i + 1]] 加進答案

為什麼這樣一定正確？

• 排序後，最小差值一定只可能出現在相鄰元素
• 不會漏掉任何可能的答案
• 時間複雜度：排序 O(n log n)，掃描 O(n)

💻 程式碼實作

class Solution {
public:
    vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        int diff = 1000000;
        for (int i = 0; i < arr.size() - 1; i++) {
            if (arr[i + 1] - arr[i] < diff) {
                diff = arr[i + 1] - arr[i];
            }
        }
        vector<vector<int>> ans;
        for (int i = 0; i < arr.size() - 1; i++) {
            if (arr[i + 1] - arr[i] == diff) {
                ans.push_back({arr[i], arr[i + 1]});
            }
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/minimum-absolute-difference/