Medium

题目描述

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

解题思路

这道题需要我们在替换最多一个元素的情况下，最小化两个数组的绝对差值和。

核心思路：

  1. 贪心策略：我们需要找到替换某个位置能带来最大收益的方案。对于位置 i，如果我们用 nums1 中的某个值 val 替换 nums1[i]，收益为 |nums1[i] - nums2[i]| - |val - nums2[i]|。

  2. 二分查找优化：对于每个位置 i，我们需要在 nums1 中找到最接近 nums2[i] 的值。最优的替换值要么是不小于 nums2[i] 的最小值，要么是不大于 nums2[i] 的最大值。这可以通过对 nums1 排序后使用二分查找来快速找到。

  3. 算法步骤：

    • 首先计算原始的绝对差值和
    • 对 nums1 进行排序（用于二分查找）
    • 遍历每个位置，计算替换该位置能获得的最大收益
    • 选择收益最大的替换方案

  4. 二分查找细节：对于 nums2[i]，我们需要找到 nums1 中：

    • 大于等于 nums2[i] 的最小值（lower_bound）
    • 小于等于 nums2[i] 的最大值（前一个位置）

通过比较这两个候选值与 nums2[i] 的差值，选择更小的那个作为最佳替换值。

代码实现

class Solution {
public:
    int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
        const int MOD = 1e9 + 7;
        int n = nums1.size();
        
        // 计算原始绝对差值和
        long long totalDiff = 0;
        for (int i = 0; i < n; i++) {
            totalDiff += abs(nums1[i] - nums2[i]);
        }
        
        // 对nums1排序以便二分查找
        vector<int> sorted_nums1 = nums1;
        sort(sorted_nums1.begin(), sorted_nums1.end());
        
        long long maxBenefit = 0;
        
        // 尝试替换每个位置
        for (int i = 0; i < n; i++) {
            int originalDiff = abs(nums1[i] - nums2[i]);
            
            // 二分查找最接近nums2[i]的值
            auto it = lower_bound(sorted_nums1.begin(), sorted_nums1.end(), nums2[i]);
            
            // 检查大于等于nums2[i]的最小值
            if (it != sorted_nums1.end()) {
                int newDiff = abs(*it - nums2[i]);
                maxBenefit = max(maxBenefit, (long long)(originalDiff - newDiff));
            }
            
            // 检查小于nums2[i]的最大值
            if (it != sorted_nums1.begin()) {
                it--;
                int newDiff = abs(*it - nums2[i]);
                maxBenefit = max(maxBenefit, (long long)(originalDiff - newDiff));
            }
        }
        
        return (totalDiff - maxBenefit) % MOD;
    }
};

class Solution:
    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(nums1)
        
        # 计算原始绝对差值和
        total_diff = sum(abs(nums1[i] - nums2[i]) for i in range(n))
        
        # 对nums1排序以便二分查找
        sorted_nums1 = sorted(nums1)
        
        max_benefit = 0
        
        # 尝试替换每个位置
        for i in range(n):
            original_diff = abs(nums1[i] - nums2[i])
            
            # 二分查找最接近nums2[i]的值
            import bisect
            pos = bisect.bisect_left(sorted_nums1, nums2[i])
            
            # 检查大于等于nums2[i]的最小值
            if pos < n:
                new_diff = abs(sorted_nums1[pos] - nums2[i])
                max_benefit = max(max_benefit, original_diff - new_diff)
            
            # 检查小于nums2[i]的最大值
            if pos > 0:
                new_diff = abs(sorted_nums1[pos - 1] - nums2[i])
                max_benefit = max(max_benefit, original_diff - new_diff)
        
        return (total_diff - max_benefit) % MOD

public class Solution {
    public int MinAbsoluteSumDiff(int[] nums1, int[] nums2) {
        const int MOD = 1000000007;
        int n = nums1.Length;
        
        // 计算原始绝对差值和
        long totalDiff = 0;
        for (int i = 0; i < n; i++) {
            totalDiff += Math.Abs(nums1[i] - nums2[i]);
        }
        
        // 对nums1排序以便二分查找
        int[] sortedNums1 = new int[n];
        Array.Copy(nums1, sortedNums1, n);
        Array.Sort(sortedNums1);
        
        long maxBenefit = 0;
        
        // 尝试替换每个位置
        for (int i = 0; i < n; i++) {
            int originalDiff = Math.Abs(nums1[i] - nums2[i]);
            
            // 二分查找最接近nums2[i]的值
            int pos = Array.BinarySearch(sortedNums1, nums2[i]);
            if (pos < 0) pos = ~pos;
            
            // 检查大于等于nums2[i]的最小值
            if (pos < n) {
                int newDiff = Math.Abs(sortedNums1[pos] - nums2[i]);
                maxBenefit = Math.Max(maxBenefit, originalDiff - newDiff);
            }
            
            // 检查小于nums2[i]的最大值
            if (pos > 0) {
                int newDiff = Math.Abs(sortedNums1[pos - 1] - nums2[i]);
                maxBenefit = Math.Max(maxBenefit, originalDiff - newDiff);
            }
        }
        
        return (int)((totalDiff - maxBenefit) % MOD);
    }
}

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var minAbsoluteSumDiff = function(nums1, nums2) {
    const MOD = 1e9 + 7;
    const n = nums1.length;
    
    // 计算原始绝对差值和
    let totalDiff = 0;
    for (let i = 0; i < n; i++) {
        totalDiff += Math.abs(nums1[i] - nums2[i]);
    }
    
    // 对nums1排序以便二分查找
    const sortedNums1 = [...nums1].sort((a, b) => a - b);
    
    let maxBenefit = 0;
    
    // 二分查找函数
    const binarySearch = (arr, target) => {
        let left = 0, right = arr.length;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    };
    
    // 尝试替换每个位置
    for (let i = 0; i < n; i++) {
        const originalDiff = Math.abs(nums1[i] - nums2[i]);
        
        // 二分查找最接近nums2[i]的值
        const pos = binarySearch(sortedNums1, nums2[i]);
        
        // 检查大于等于nums2[i]的最小值
        if (pos < n) {
            const newDiff = Math.abs(sortedNums1[pos] - nums2[i]);
            maxBenefit = Math.max(maxBenefit, originalDiff - newDiff);
        }
        
        // 检查小于nums2[i]的最大值
        if (pos > 0) {
            const newDiff = Math.abs(sortedNums1[pos - 1] - nums2[i]);
            maxBenefit = Math.max(maxBenefit, originalDiff - newDiff);
        }
    }
    
    return (totalDiff - maxBenefit) % MOD;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
排序O(n log n)O(n)
二分查找O(n log n)O(1)
总体O(n log n)O(n)

其中 n 为数组长度。空间复杂度主要用于排序后的数组副本。

相关题目