Question

1818. Minimum Absolute Sum Difference

中文文档

Description

You are given two positive integer arrays nums1 and nums2, both of length n.

The absolute sum difference of arrays nums1 and nums2 is defined as the sum of |nums1[i] - nums2[i]| for each 0 <= i < n (0-indexed).

You can replace at most one element of nums1 with any other element in nums1 to minimize the absolute sum difference.

Return the _minimum absolute sum difference after replacing at most one element in the array nums1._ Since the answer may be large, return it modulo 109 + 7.

|x| is defined as:

• x if x >= 0, or
• -x if x < 0.

 

Example 1:

Input: nums1 = [1,7,5], nums2 = [2,3,5]
Output: 3
Explanation: There are two possible optimal solutions:
- Replace the second element with the first: [1,7,5] => [1,1,5], or
- Replace the second element with the third: [1,7,5] => [1,5,5].
Both will yield an absolute sum difference of |1-2| + (|1-3| or |5-3|) + |5-5| = 3.

Example 2:

Input: nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10]
Output: 0
Explanation: nums1 is equal to nums2 so no replacement is needed. This will result in an 
absolute sum difference of 0.

Example 3:

Input: nums1 = [1,10,4,4,2,7], nums2 = [9,3,5,1,7,4]
Output: 20
Explanation: Replace the first element with the second: [1,10,4,4,2,7] => [10,10,4,4,2,7].
This yields an absolute sum difference of |10-9| + |10-3| + |4-5| + |4-1| + |2-7| + |7-4| = 20

 

Constraints:

• n == nums1.length
• n == nums2.length
• 1 <= n <= 105
• 1 <= nums1[i], nums2[i] <= 105

Solutions

Solution 1: Sorting + Binary Search

According to the problem, we can first calculate the absolute difference sum of nums1 and nums2 without any replacements, denoted as $s$.

Next, we enumerate each element $nums1[i]$ in nums1, replacing it with the element closest to $nums2[i]$ that also exists in nums1. Therefore, before the enumeration, we can make a copy of nums1, resulting in the array nums, and sort nums. Then, we perform a binary search in nums for the element closest to $nums2[i]$, denoted as $nums[j]$, and calculate $|nums1[i] - nums2[i]| - |nums[j] - nums2[i]|$, updating the maximum value of the difference $mx$.

Finally, we subtract $mx$ from $s$, which is the answer. Note the modulus operation.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array 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;
}