1818.绝对差值和

链接：1818.绝对差值和
难度：Medium
标签：数组、二分查找、有序集合、排序
简介：给你两个正整数数组 nums1 和 nums2 ，数组的长度都是 n 。在替换数组 nums1 中最多一个元素 之后 ，返回最小绝对差值和。

题解 1 - typescript

• 编辑时间：2021-07-14
• 执行用时：224ms
• 内存消耗：55.9MB
• 编程语言：typescript
• 解法介绍：对每一位进行查找最近值。

function minAbsoluteSumDiff(nums1: number[], nums2: number[]): number {
  const len = nums1.length;
  const nums: number[] = new Array(len).fill(0).map((_, i) => Math.abs(nums1[i] - nums2[i]));
  nums1.sort((a, b) => a - b);
  const sum = nums.reduce((total, cur) => total + cur, 0);
  let ans = sum;
  for (let i = 0; i < len; i++) ans = Math.min(ans, sum - nums[i] + findMin(i));
  return ans % (10 ** 9 + 7);
  function findMin(index: number): number {
    const num2 = nums2[index];
    let left = 0;
    let right = len - 1;
    while (left < right) {
      const mid = (left + right) >> 1;
      const midNum = nums1[mid];
      if (midNum < num2) left = mid + 1;
      else if (midNum > num2) right = mid - 1;
      else {
        left = mid;
        break;
      }
    }
    return Math.min(
      Math.abs(nums1[left] - num2),
      left > 0 ? Math.abs(nums1[left - 1] - num2) : Infinity,
      left < len - 1 ? Math.abs(nums1[left + 1] - num2) : Infinity
    );
  }
}