Question

1818. 绝对差值和

English Version

题目描述

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

解法

方法一：排序 + 二分查找

根据题意，我们可以先计算出在不进行替换的情况下，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 的长度。

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

class Solution {
  public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
    final int mod = (int) 1e9 + 7;
    int[] nums = nums1.clone();
    Arrays.sort(nums);
    int s = 0, n = nums.length;
    for (int i = 0; i < n; ++i) {
      s = (s + Math.abs(nums1[i] - nums2[i])) % mod;
    }
    int mx = 0;
    for (int i = 0; i < n; ++i) {
      int d1 = Math.abs(nums1[i] - nums2[i]);
      int d2 = 1 << 30;
      int j = search(nums, nums2[i]);
      if (j < n) {
        d2 = Math.min(d2, Math.abs(nums[j] - nums2[i]));
      }
      if (j > 0) {
        d2 = Math.min(d2, Math.abs(nums[j - 1] - nums2[i]));
      }
      mx = Math.max(mx, d1 - d2);
    }
    return (s - mx + mod) % mod;
  }

  private int search(int[] nums, int x) {
    int left = 0, right = nums.length;
    while (left < right) {
      int mid = (left + right) >>> 1;
      if (nums[mid] >= x) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
}

class Solution {
public:
  int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
    const int mod = 1e9 + 7;
    vector<int> nums(nums1);
    sort(nums.begin(), nums.end());
    int s = 0, n = nums.size();
    for (int i = 0; i < n; ++i) {
      s = (s + abs(nums1[i] - nums2[i])) % mod;
    }
    int mx = 0;
    for (int i = 0; i < n; ++i) {
      int d1 = abs(nums1[i] - nums2[i]);
      int d2 = 1 << 30;
      int j = lower_bound(nums.begin(), nums.end(), nums2[i]) - nums.begin();
      if (j < n) {
        d2 = min(d2, abs(nums[j] - nums2[i]));
      }
      if (j) {
        d2 = min(d2, abs(nums[j - 1] - nums2[i]));
      }
      mx = max(mx, d1 - d2);
    }
    return (s - mx + mod) % mod;
  }
};

func minAbsoluteSumDiff(nums1 []int, nums2 []int) int {
  n := len(nums1)
  nums := make([]int, n)
  copy(nums, nums1)
  sort.Ints(nums)
  s, mx := 0, 0
  const mod int = 1e9 + 7
  for i, a := range nums1 {
    b := nums2[i]
    s = (s + abs(a-b)) % mod
  }
  for i, a := range nums1 {
    b := nums2[i]
    d1, d2 := abs(a-b), 1<<30
    j := sort.SearchInts(nums, b)
    if j < n {
      d2 = min(d2, abs(nums[j]-b))
    }
    if j > 0 {
      d2 = min(d2, abs(nums[j-1]-b))
    }
    mx = max(mx, d1-d2)
  }
  return (s - mx + mod) % mod
}

func abs(x int) int {
  if x < 0 {
    return -x
  }
  return x
}

function minAbsoluteSumDiff(nums1: number[], nums2: number[]): number {
  const mod = 10 ** 9 + 7;
  const nums = [...nums1];
  nums.sort((a, b) => a - b);
  const n = nums.length;
  let s = 0;
  for (let i = 0; i < n; ++i) {
    s = (s + Math.abs(nums1[i] - nums2[i])) % mod;
  }
  let mx = 0;
  for (let i = 0; i < n; ++i) {
    const d1 = Math.abs(nums1[i] - nums2[i]);
    let d2 = 1 << 30;
    let j = search(nums, nums2[i]);
    if (j < n) {
      d2 = Math.min(d2, Math.abs(nums[j] - nums2[i]));
    }
    if (j) {
      d2 = Math.min(d2, Math.abs(nums[j - 1] - nums2[i]));
    }
    mx = Math.max(mx, d1 - d2);
  }
  return (s - mx + mod) % mod;
}

function search(nums: number[], x: number): number {
  let left = 0;
  let right = nums.length;
  while (left < right) {
    const mid = (left + right) >> 1;
    if (nums[mid] >= x) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return left;
}

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var minAbsoluteSumDiff = function (nums1, nums2) {
  const mod = 10 ** 9 + 7;
  const nums = [...nums1];
  nums.sort((a, b) => a - b);
  const n = nums.length;
  let s = 0;
  for (let i = 0; i < n; ++i) {
    s = (s + Math.abs(nums1[i] - nums2[i])) % mod;
  }
  let mx = 0;
  for (let i = 0; i < n; ++i) {
    const d1 = Math.abs(nums1[i] - nums2[i]);
    let d2 = 1 << 30;
    let j = search(nums, nums2[i]);
    if (j < n) {
      d2 = Math.min(d2, Math.abs(nums[j] - nums2[i]));
    }
    if (j) {
      d2 = Math.min(d2, Math.abs(nums[j - 1] - nums2[i]));
    }
    mx = Math.max(mx, d1 - d2);
  }
  return (s - mx + mod) % mod;
};

function search(nums, x) {
  let left = 0;
  let right = nums.length;
  while (left < right) {
    const mid = (left + right) >> 1;
    if (nums[mid] >= x) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return left;
}