绝对差值和

标签: 数组 二分查找 有序集合 排序

难度: Medium

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

 

提示：

  • n == nums1.length
  • n == nums2.length
  • 1 <= n <= 105
  • 1 <= nums1[i], nums2[i] <= 105

Submission

运行时间: 104 ms

内存: 29.4 MB

class Solution:
    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:
        s = sorted(nums1)
        l = len(nums1)
        ret, m = 0, 10 ** 9 + 7
        r = 0
        for a, b in zip(nums1, nums2):
            t = abs(a - b)
            ret += t
            if t > r:
                pl = min(l - 1, bisect.bisect_left(s, b))
                na = s[pl]
                nt = abs(na - b)
                if pl - 1 >= 0:
                    nt = min(nt, abs(s[pl - 1] - b))
                r = max(r, t - nt)

        return (ret - r) % m

Explain

此题解的策略是首先计算出原始数组 nums1 和 nums2 之间的绝对差值和。然后尝试通过替换 nums1 中的每个元素来找到可能降低这个差值和的最大幅度。为了实现这一点，我们首先对 nums1 进行排序，以便于后续可以快速找到最接近 nums2 中任意元素 b 的 nums1 中的元素。对于 nums1 和 nums2 中的每个元素对 (a, b)，我们计算原始差值 t = |a - b| 并累加到总和 ret 中。接着，使用二分搜索在排序后的 nums1 中查找最接近 b 的元素，计算如果替换了这个元素后的新差值 nt。我们记录下所有可能的替换中，减少的最大差值 r。最终答案即为原始差值和减去这个最大减少值 r，并对 10^9+7 取余。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:
        s = sorted(nums1)  # 对nums1进行排序
        l = len(nums1)
        ret, m = 0, 10 ** 9 + 7
        r = 0  # r记录最大的差值减少量
        for a, b in zip(nums1, nums2):
            t = abs(a - b)
            ret += t  # 累加原始差值
            if t > r: # 如果当前差值大于已记录的最大减少量
                pl = min(l - 1, bisect.bisect_left(s, b))
                na = s[pl]  # 找到最接近b的元素
                nt = abs(na - b)
                if pl - 1 >= 0:
                    nt = min(nt, abs(s[pl - 1] - b))  # 检查前一个元素是否更接近
                r = max(r, t - nt)  # 更新最大减少量

        return (ret - r) % m  # 返回调整后的最小绝对差值和

Explore

尽管同时替换多个元素可能会进一步降低绝对差值和，但这样会大幅增加问题的复杂性和计算量。考虑到每个元素都有多种替换可能，同时替换多个元素会导致情况组合指数级增长，这在算法设计中是不可行的。因此，我们通常采用贪心策略，即通过每次只替换一个元素来寻找最佳单次替换，从而在可接受的时间复杂度内获得一个较优解。

如果在使用二分搜索找到多个具有相同最小差值的元素，通常选择任何一个都可以，因为它们提供相同的差值减少。然而，为了保持一致性和可能的最小化边际效应，通常选择第一个找到的或者位置最靠前的元素。这样做可以保持算法的简洁性和实现的直观性。

通过对nums1进行排序和使用二分搜索，我们将查找最接近的元素的时间复杂度从O(n)降低到O(log n)。这意味着对于每个元素b，我们可以以对数时间复杂度找到接近的值，而不是线性时间。因此，整体算法的时间复杂度从O(n^2)（对于每对元素进行遍历）降低到O(n log n)（排序nums1和对每个元素b进行二分搜索）。这显著提高了算法处理大数据集的能力。

在计算最大减少量r时，检查当前差值t是否大于已记录的最大减少量r是为了确保我们只考虑那些能实现最大绝对差值减少的元素替换。如果当前差值t本身就不大，即使通过替换减少了差值，也不会对总和产生显著影响。因此，我们专注于那些原始差值较大的情况，通过尝试替换来达到最大的减少效果。这种方法可以更有效地减少总的绝对差值和。