绝对差值和

力扣 1818. 绝对差值和

题目说明

给你两个正整数数组 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
提示：
- n == nums1.length
- n == nums2.length
- 1 <= n <= 105
- 1 <= nums1[i], nums2[i] <= 10^5

示例

示例 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：

1
2
3

输入：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

笔者理解

此题是一道数组算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现此题用贪心需要做出一些调整，因为修改产生的最大差值不一定是修改差距最大的元素产生的，让我们来看看具体如何实现的吧。

实现

class Solution {
    /*
     * HashSet
     * 取余
     */
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        int result = 0;
        int n = nums1.length;
        int MOD = 1000000007;

        // 用TreeSet来存储数组1中的元素
        TreeSet<Integer> set = new TreeSet<>();
        for (int i : nums1) {
            set.add(i);
        }

        
        // 更改方案能减少的最大差值
        int max = 0;
        for (int i = 0; i < n; i++) {
            int temp = Math.abs(nums1[i] - nums2[i]);

            int num2 = nums2[i];

            // 寻找num2在数组1中对应的上边界和下边界（也就是最接近于num2的大于他的数和小于他的数）
            int floor = set.floor(num2) == null? -100000: set.floor(num2);
            int ceil = set.ceiling(num2) == null? -100000: set.ceiling(num2);

            int floorGap = Math.abs(floor - num2);
            int ceilGap = Math.abs(ceil - num2);

            // 比较这次修改能带来的最大差值
            max = Math.max(max, Math.max(temp - floorGap, temp - ceilGap));
                
            // (a + b) % c = (a%c + b%c) % c
            result = (result % MOD + temp % MOD) % MOD;
        }

        // 防止溢出
        return (result - max + MOD) % MOD;
    }
}