1818. 最小絕對差值和

小貼士：lower_bound(nums.begin(), nums.end(), x) 能找到第一個>= x數字所在的位置

思路

根據題意，可以轉換至多一個數字為nums1[i]中的任意數字。
相當於在nums2選至多一個數字，配對nums1中的任何一個數字。

怎麼使用這個配對機會？讓總距離變的最小？
自然要選擇距離最遠的那一對nums1[i], nums2[i]數字，
換一個距離更接近nums2[i]的數字nums1[idx]。

因此，排序nums1之後，
計算讓nums2[i]使用配對機會能省下來的距離（找到最接近nums2[i]的nums[idx]），
最後選擇最好的那一個。

程式碼

排序 + 二分查找

class Solution {
public:
    int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
        const int MOD = 1e9 + 7;
        int n = nums1.size();
        vector<int> sorted = nums1;
        ranges::sort(sorted);
        long long diff = 0;
        int mx_save = 0; // 最多能省去多少距離
        for(int i = 0; i < n; ++i) {
            int curDiff = abs(nums1[i] - nums2[i]);
            diff += curDiff;            
            // nums2[i] 找到在 nums1 中, 跟自己最接近的數字
            int idx = lower_bound(sorted.begin(), sorted.end(), nums2[i]) - sorted.begin();

            // 原先: abs(nums1[i] - nums2[i])
            // 後來: abs(nums1[idx] - nums2[i]);
            // 能省去 abs(nums1[idx] - nums2[i]) - abs(nums1[i] - nums2[i]);
            if(0 < idx && idx < n) {
                mx_save = max({mx_save, 
                               curDiff - abs(nums2[i] - sorted[idx - 1]), 
                               curDiff - abs(nums2[i] - sorted[idx])}); 
            }
            else if(idx == n) { // 最尾端
                mx_save = max(mx_save, curDiff - abs(nums2[i] - sorted[idx - 1])); 
            }
            else { // 最前端
                mx_save = max(mx_save, curDiff - abs(nums2[i] - sorted[idx])); 
            }
        }
        return (diff - mx_save) % MOD;
    }
};

複雜度分析

• 時間複雜度：$(n\log{n})$
• 空間複雜度：$(n)$