| 题目链接 | 1818. 绝对差值和 |
|---|---|
| 思路 | 排序+二分 |
| 题解链接 | 运用「二分」找最佳替换方案 |
| 关键点 | 转换为查找最小值delta：对nums1进行排序后，从中二分查找nums2[i]的最接近值（考虑到绝对值，需要检查left & right两个位置） |
| 时间复杂度 | \(O(n\log n)\) |
| 空间复杂度 | \(O(n)\) |
代码实现：
class Solution:
def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:
total = 0
sorted_ = sorted(nums1)
n = len(nums1)
delta = inf
for i in range(n):
diff = abs(nums1[i] - nums2[i])
total += diff
left, right = -1, n
while left + 1 < right:
mid = (left+right) // 2
if sorted_[mid] < nums2[i]:
left = mid
else:
right = mid
if left >= 0:
delta = min(delta, abs(sorted_[left] - nums2[i]) - diff)
if right < n:
delta = min(delta, abs(sorted_[right] - nums2[i]) - diff)
return (total + delta) % (10 ** 9 + 7)
Python-标准库
class Solution:
def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:
total = 0
sorted_ = sorted(nums1)
n = len(nums1)
delta = inf
for i in range(n):
diff = abs(nums1[i] - nums2[i])
total += diff
right = bisect_left(sorted_, nums2[i])
left = right-1
if left >= 0:
delta = min(delta, abs(sorted_[left] - nums2[i]) - diff)
if right < n:
delta = min(delta, abs(sorted_[right] - nums2[i]) - diff)
return (total + delta) % (10 ** 9 + 7)