题目：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
示例 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.lengthn == nums2.length1 <= n <= 1051 <= nums1[i], nums2[i] <= 105
解题思路
-
题目核心：通过替换
nums1中的一个元素，使得nums1和nums2之间的绝对差值和最小化。 -
二分查找实现步骤：
- 计算初始绝对差值和
- 对
nums1排序 - 遍历
nums1并尝试替换每个元素- 二分查找找到最接近
nums2[i]的值 - 检查
pos和pos-1位置的值
- 二分查找找到最接近
- 取模并返回结果
暴力解法(超时)
from typing import List
class Solution:
def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:
MOD = 10**9 + 7
n = len(nums1)
# 计算初始的绝对差值和
initial_sum = sum(abs(nums1[i] - nums2[i]) for i in range(n))
min_sum = initial_sum
# 尝试替换 nums1 中的每个元素
for i in range(n):
current_diff = abs(nums1[i] - nums2[i])
# 遍历 nums1 中的每个元素作为替换候选
for j in range(n):
if i != j:
new_diff = abs(nums1[j] - nums2[i])
new_sum = initial_sum - current_diff + new_diff
min_sum = min(min_sum, new_sum)
return min_sum % MOD
# 示例测试用例
solution = Solution()
print(solution.minAbsoluteSumDiff([1, 10, 4, 4, 2, 7], [9, 3, 5, 1, 7, 4])) # 应输出：20
二分查找
from bisect import bisect_left
from typing import List
class Solution:
def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:
MOD = 10**9 + 7
n = len(nums1)
sorted_nums1 = sorted(nums1)
# 初始绝对差值和
initial_sum = sum(abs(nums1[i] - nums2[i]) for i in range(n))
min_sum = initial_sum
for i in range(n):
current_diff = abs(nums1[i] - nums2[i])
# 二分查找找到最接近 nums2[i] 的值
pos = bisect_left(sorted_nums1, nums2[i])
# 检查 pos 位置的值
if pos < n:
new_diff = abs(sorted_nums1[pos] - nums2[i])
new_sum = initial_sum - current_diff + new_diff
min_sum = min(min_sum, new_sum)
# 检查 pos-1 位置的值
if pos > 0:
new_diff = abs(sorted_nums1[pos - 1] - nums2[i])
new_sum = initial_sum - current_diff + new_diff
min_sum = min(min_sum, new_sum)
return min_sum % MOD
反思
- 为什么要找到替换为最接近
nums2[i]的值？
如果我们想让这个差值最小，我们需要让 nums1[i] 尽量接近 nums2[i]。因为：
- 当两个数接近时，它们的差值
|nums1[i] - nums2[i]|也会很小。 - 例如，如果
nums2[i] = 5，而我们有两个候选值4和7，显然4比7更接近5，因此|4 - 5|比|7 - 5|小。
- 为什么要使用
bisect_left，而不是bisect_right？
bisect_left 返回的是数组中第一个大于或等于查找值的位置。bisect_right 返回的是数组中第一个大于查找值的位置。
假设我们有一个排序数组 sorted_nums1 = [1, 2, 4, 4, 7, 10]，我们要查找 nums2[i] = 4 在这个数组中的插入点。
bisect_left(sorted_nums1, 4)返回 2，因为sorted_nums1[2]是 4，这是第一个大于或等于 4 的位置。bisect_right(sorted_nums1, 4)返回 4，因为sorted_nums1[4]是 7，这是第一个大于 4 的位置。
在这一题目中，我们需要找到最接近 nums2[i] 的值，以尽可能减少绝对差值和。使用 bisect_left 可以帮助我们找到最接近的值，并确保我们不会错过等于 nums2[i] 的值。
- 为什么要检查两个位置（
pos和pos-1）？
当我们使用 bisect_left(sorted_nums1, nums2[i]) 时，我们得到的是 nums2[i] 在 sorted_nums1 中的插入位置 pos。这个位置表示在保持数组有序的情况下，nums2[i] 应该插入的位置。
pos位置解释：sorted_nums1[pos]是第一个大于或等于nums2[i]的元素。因此，sorted_nums1[pos]可能是一个接近nums2[i]的候选值。pos-1位置解释：sorted_nums1[pos-1]是小于nums2[i]的最大元素。由于pos-1位置的元素也是接近nums2[i]的另一个候选值，因此我们也需要检查这个位置。
所以，检查这两个位置的原因为：
- 全面覆盖可能的候选值
- 确保找到最优解
pos < n与pos >0该如何理解？
当我们使用 bisect_left(sorted_nums1, nums2[i]) 时，得到的 pos 是插入位置，即第一个大于或等于 nums2[i] 的位置。这个位置有可能是数组的末尾，因此我们需要检查 pos < n，确保 pos 在有效范围内。
为什么要检查 pos < n ？
- 防止数组越界：如果
pos恰好等于n，说明nums2[i]大于sorted_nums1中的所有元素。在这种情况下，访问sorted_nums1[pos]会导致数组越界错误。 - 确保有效访问：只有在
pos < n时，我们才能安全地访问sorted_nums1[pos]，因为这时pos是一个有效的索引。
类似地，我们还需要检查 pos-1 的位置，以便找到小于 nums2[i] 的最大值。为了确保 pos-1 在有效范围内，我们需要检查 pos > 0。
为什么要检查 pos > 0 ？
- 防止数组越界：如果
pos恰好等于 0，说明nums2[i]小于或等于sorted_nums1中的所有元素。在这种情况下，访问sorted_nums1[pos-1]会导致数组越界错误。 - 确保有效访问：只有在
pos > 0时，我们才能安全地访问sorted_nums1[pos-1]，因为这时pos-1是一个有效的索引。