【LeetCode/力扣】1818. 絕對內插補點和

1 題目描述

題目連結：https://leetcode-cn.com/problems/minimum-absolute-sum-difference/添加連結描述

給你兩個正整數數組 nums1 和 nums2 ，數組的長度都是 n 。

數組 nums1 和 nums2 的 絕對內插補點和 定義為所有 |nums1[i] - nums2[i]|（0 <= i < n）的 總和（下标從 0 開始）。

你可以選用 nums1 中的 任意一個 元素來替換 nums1 中的 至多 一個元素，以 最小化 絕對內插補點和。

在替換數組 nums1 中最多一個元素 之後 ，傳回最小絕對內插補點和。因為答案可能很大，是以需要對 109 + 7 取餘 後傳回。

|x| 定義為：

如果 x >= 0 ，值為 x ，或者

如果 x <= 0 ，值為 -x

示例 1：

輸入：nums1 = [1,7,5], nums2 = [2,3,5]

輸出：3

解釋：有兩種可能的最優方案：

• 将第二個元素替換為第一個元素：[1,7,5] => [1,1,5] ，或者

• 将第二個元素替換為第三個元素：[1,7,5] => [1,5,5]

  兩種方案的絕對內插補點和都是 |1-2| + (|1-3| 或者 |5-3|) + |5-5| = 3

  示例 2：

輸入：nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10]

輸出：0

解釋：nums1 和 nums2 相等，是以不用替換元素。絕對內插補點和為 0

示例 3：

輸入：nums1 = [1,10,4,4,2,7], nums2 = [9,3,5,1,7,4]

輸出：20

解釋：将第一個元素替換為第二個元素：[1,10,4,4,2,7] => [10,10,4,4,2,7]

絕對內插補點和為 |10-9| + |10-3| + |4-5| + |4-1| + |2-7| + |7-4| = 20

2 代碼/C++

class Solution {
public:
    static constexpr int mod = 1'000'000'007; // constexpr定義編譯器常量，大數可以用逗号隔開
    int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        vector<int>rec(nums1); // vector的定義初始化，複制另外一個vector
        int maxn = 0, s = 0;
        sort(rec.begin(), rec.end()); // 排序，從小到大
        for (int i=0; i<n; ++i){
            int diff = abs(nums1[i] - nums2[i]);
            s = (s + diff) % mod;
            // lower_bound 采用二分法尋找第一個大于等于target的數的位置，不存在則傳回end，減begin得到其在數組下标
            // upper_bound 采用二分法尋找第一個小于等于target的數的位置，不存在則傳回end，減begin得到其在數組下标
            int j = lower_bound(rec.begin(), rec.end(), nums2[i]) - rec.begin(); 
            if (j<n){
                // 第一個大于等于nums2[i]的數
                // 如果j是0，則表示rec中的數都大于等于target，傳回最小的數，也就是下标0
                maxn = max(maxn, diff - (rec[j] - nums2[i])); 
            }
            if (j>0){
                // 最後一個小于nums2[i]的數
                // 如果j是n，則表示rec中的數都小于target，傳回最大的數，也就是下标n-1
                maxn = max(maxn, diff - (nums2[i] - rec[j-1]));
            }
        }
        return (s - maxn + mod) % mod; // 防止s-maxn<mod
    }
};