题目描述

给你两个正整数数组 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

样例

输入

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的每一个位置（对nums1去重一下）

• 每次枚举nums1[i]时，用lower_bound()从nums1中找出第一个大于等于nums2[i]的数(it),同时也找出第一个比nums2[i]小的数(it–)。
• 分别用这两个数替换nums[i],比较用这两个数修改后的nums1，哪个的绝对差值更小

时间复杂度 $O(nlogn)$

参考文献

C++ 代码

class Solution {
public:
    const int mod = 1e9 + 7;
    int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        set<long long> st;
        long long all = 0, ans = 0;
        for (int i = 0; i < n; ++i) {
            st.insert(nums1[i]);
            all += abs(nums1[i] - nums2[i]);
        }
        long long maxn = 0;
        for (int i = 0; i < n; ++i) {
            auto it = st.lower_bound(nums2[i]);
            long long cur = abs(nums1[i] - nums2[i]);
            //用set去重, 每次it = lower_bound()到>=nums2[i]中最接近nums2[i]的数, 同时要考虑<nums2[i]中最接近的数, 这时候将it--即可.
            if (it != st.end()) {

                //maxn表示替换之前和替换之后相差的值
                maxn = max(maxn, cur - abs(*it - nums2[i]));
            }
            if (it != st.begin()) {
                maxn = max(maxn, cur - abs(*(--it) - nums2[i]));
            }
        }
        return (all - maxn) % mod;
    }
};