What is the main approach to solve Minimum Absolute Sum Difference?

The main approach is to use binary search over the valid answer space, sorting the arrays and testing the best replacement for each element in nums1.

What is the time complexity of the solution?

The time complexity is O(n log n) due to the sorting of nums1 and the binary search operations for each element.

Can the problem be solved without sorting?

Sorting is necessary to efficiently perform binary search and find the best replacement for each element in nums1.

What is the role of binary search in this problem?

Binary search helps to find the best element from nums1 that minimizes the absolute sum difference when tested against each element of nums2.

What are some common mistakes when solving this problem?

Common mistakes include failing to handle cases where no replacement is needed and incorrect binary search implementation leading to inefficient or incorrect solutions.

#1818

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

绝对差值和

给你两个正整数数组 nums1 和 nums2 ，数组的长度都是 n 。数组 nums1 和 nums2 的绝对差值和定义为所有 |nums1[i] - nums2[i]| （ 0 ）的总和（下标从 0 开始）。你可以选用 nums1 中的任意一个元素来替换 nums1 中的至…

数组二分查找排序有序集合

题目描述

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

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

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

在替换数组 nums1 中最多一个元素之后，返回最小绝对差值和。因为答案可能很大，所以需要对 10⁹ + 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⁵
1 <= nums1[i], nums2[i] <= 10⁵

lightbulb

解题思路

方法一：排序 + 二分查找

根据题意，我们可以先计算出在不进行替换的情况下，nums1 和 nums2 的绝对差值和，记为 $s$ 。

接下来，我们枚举 nums1 中的每个元素 $nums1[i]$ ，将其替换为与 $nums2[i]$ 最接近的元素，并且这个最接近的元素在 nums1 中。因此，我们可以在枚举之前，先复制一份 nums1，得到数组 nums，并将 nums 排序。接下来，就在 nums 中二分查找与 $nums2[i]$ 最接近的元素，记为 $nums[j]$ ，并计算 $|nums1[i] - nums2[i]| - |nums[j] - nums2[i]|$ ，更新差值 $mx$ 的最大值。

最后，我们将 $s$ 减去 $mx$ ，即为答案。注意取模操作。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 nums1 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:
        mod = 10**9 + 7
        nums = sorted(nums1)
        s = sum(abs(a - b) for a, b in zip(nums1, nums2)) % mod
        mx = 0
        for a, b in zip(nums1, nums2):
            d1, d2 = abs(a - b), inf
            i = bisect_left(nums, b)
            if i < len(nums):
                d2 = min(d2, abs(nums[i] - b))
            if i:
                d2 = min(d2, abs(nums[i - 1] - b))
            mx = max(mx, d1 - d2)
        return (s - mx + mod) % mod

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for an understanding of binary search over a sorted array.
question_mark
Test candidate's ability to identify and implement the optimal replacement strategy efficiently.
question_mark
Gauge how well the candidate handles edge cases and the upper constraint limits.

warning

常见陷阱

外企场景

error
Failing to account for the case where no replacement is needed (when nums1 is already equal to nums2).
error
Incorrectly implementing binary search, leading to suboptimal performance or incorrect answers.
error
Overcomplicating the problem by using unnecessary operations instead of relying on sorting and binary search.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Generalize the problem by allowing multiple replacements in nums1 to minimize the absolute sum difference.
arrow_right_alt
Modify the problem to handle larger constraints, such as arrays with length up to 10^6.
arrow_right_alt
Introduce the requirement of minimizing the absolute sum difference for non-positive integers in nums1 and nums2.

help

常见问题

外企场景

继续练习

#1847 最近的房间 #2251 花期内花的数目 #2659 将数组清空