绝对差值和

具体的，当我们处理到第 i 位时，假设该位的原差值为 x = abs(nums1[i] - nums2[i])x=abs(nums1[i]−nums2[i])，然后从 sorted 数组中通过二分找到最接近 nums2[i] 的值，计算一个新的差值 nd（注意要检查分割点与分割点的上一位），如果满足 nd < x 说明存在一个替换方案使得差值变小，我们使用变量 maxn 记下来这个替换方案所带来的变化，并不断更新 maxn。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
 public:
  int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
    int n = nums1.size();
    int maxn = 0;
    int mod = 1e9 + 7;
    int sum = 0;
    // 将 nums1 复制一份并排序
    vector<int> sorted(nums1.begin(), nums1.end());
    sort(sorted.begin(), sorted.end());

    for (int i = 0; i < n; i++) {
      int a = nums1[i];
      int b = nums2[i];
      // 原来数组的差值
      int d = abs(a - b);
      int l = 0, r = n - 1;
      sum = (sum + d) % mod;
      // 在 sorted 数组中查找与 nums2[i] 最接近的数，这里二分之后找到的是大于等于 nums2[i] 的第一个数，所以 sorted[l-1] 也可能是答案
      while (l < r) {
        int mid = l + r >> 1;
        if (sorted[mid] >= b) {
          r = mid;
        } else {
          l = mid + 1;
        }
      }
      int nd = abs(sorted[l] - b);
      if (l - 1 >= 0) {
        // sorted[l-1] 是否比 sorted[l] 更优
        nd = min(nd, abs(sorted[l - 1] - b));
      }
      if (d - nd > 0) maxn = max(maxn, d - nd);
    }
    return (sum - maxn + mod) % mod;
  }
};