1818. 绝对差值和

题目描述

给你两个正整数数组 nums1 和 nums2 ，数组的长度都是 n 。

数组 nums1 和 nums2 的 绝对差值和 定义为所有 $|nums1[i]-nums2[i]|（0<=i<n）$的 总和（下标从 0 开始）。

你可以选用 nums1 中的 任意一个 元素来替换 nums1 中的 至多 一个元素，以 最小化 绝对差值和。

在替换数组 nums1 中最多一个元素 之后 ，返回最小绝对差值和。因为答案可能很大，所以需要对 $10^9+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

提示

• $n==nums1.length$
• $n==nums2.length$
• $1<=n<=10^5$
• $1<=nums1[i],nums2[i]<=10^5$

方法：排序 + 二分查找

解题思路

先将 $nums1$ 数组拷贝一份，并进行排序，以便二分查找时用到。

由题意我们可以分析出，总绝对差值和等于 n 对 $|nums1[i]-nums2[i]|$ 的和，要使这个总绝对差值和最小，我们就得使一对 $|nums1[i]-nums2[i]|$ 的值最小。

遍历每一个 $nums2[i]$，一边用 $sum$ 累计每一对 $|nums1[i]-nums2[i]|$ 的和；一边利用二分查找，找到一个 $nums1[j]$ 替换 $nums1[i]$，使得 $|nums1[j]-nums2[i]|$ 的值最小。最后用 $maxn$ 来记录 $|nums1[i]-nums2[i]|-|nums1[j]-nums2[i]|$ 差值最大的那一组值。然后用 $sum$ 减去 $maxn$ 便能使得总绝对差值和最小。

那如何找到离 $nums2[i]$ 最近的一个 $nums1[i]$，使得 $|nums1[j]-nums2[i]|$ 的值最小呢 ？

我先我们使用 $lower\_bound()$ 函数找到 $nums1$ 中大于等于 $nums2[i]$ 的最小值下标 $j$，但此时的 $nums1[j]$ 并不是离 $nums2[i]$ 的最近的一个值。

我们来分析 $lower\_bound和upper\_bound$ 函数的用法：
如果数组为 $[1,2,2,4]$，使用 $lower\_bound$，返回数组中 $>=target$ 的第一个元素的下标

如果数组为 $[1,2,2,4]$，使用 $upper\_bound$，返回数组中 $>target$ 的第一个元素的下标

因此，我们把 $lower\_bound$ 查找到的下标 $j$ 分析一下：

• 如果 $j==n$，此时说明没有找到 $>=target$ 的第一个元素，只能取 $n-1$，所以 $j=n-1$；
• 如果 $1<=j<n$，此时说明找到了 $>=target$ 的第一个元素，但是不能确保 $nums1[j]$ 一定就是离 $nums2[i]$ 最近的值，可以为 $nums1[j]$，也可以为 $nums1[j-1]$；
• 如果 $j==0$，此时说明 $>=target$ 的第一个元素就是 $nums[0]$。

综合以上 3 种情况，我们把它合并成如下代码所示：

if(j < n)
	maxn = max(maxn, diff - (rec[j] - nums2[i]));
if(j > 0)
    maxn = max(maxn, diff - (nums2[i] - rec[j - 1]));
1
2
3
4

这样 $1<=j<n$ 的两种取值情况也都会被考虑到，无论是 $j==n$ 或者 $j==0$ 都只会被考虑到一次。

代码

class Solution {
public:
    static constexpr int mod = 1e9 + 7;
    int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
        vector<int> rec(nums1);
        sort(rec.begin(), rec.end());
        int n = nums1.size();
        int sum = 0;
        int maxn = 0;
        for(int i = 0; i < n; i++)
        {
            int diff = abs(nums1[i] - nums2[i]);
            sum = (sum + diff) % mod;
            int j = lower_bound(rec.begin(), rec.end(), nums2[i]) - rec.begin();
            if(j < n)
                maxn = max(maxn, diff - (rec[j] - nums2[i]));
            if(j > 0)
                maxn = max(maxn, diff - (nums2[i] - rec[j - 1]));
        }
        return (sum - maxn + mod) % mod;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

复杂度分析

• 时间复杂度：$O(nlogn)$。排序的时间复杂度为 $O(nlogn)$；而二分查找的时间复杂度为 $O(nlogn)$，而每一个 $nums1[i]$ 都需要一次二分查找，所以时间复杂度为 $O(nlogn)$。因此，整体时间复杂度为 $O(nlogn)$。
• 空间复杂度：$O(n)$。$n$ 为数组 $nums1$ 的长度。