一、题目

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

善于使用已有的数据结构可以快速解题，本题很容易误解用贪心可以很好地求解，但存在以下情况，当两个数组分别为{5, 5, 5, 4}和{10, 8, 7, 6}时，无法使用贪心求解，只能根据nums2的每个元素nums2[i]，找在nums1中最贴近nums2[i]的数字，再与原来的差值做对比，找到减少最小绝对差值的最大值，记录下来

三、代码

1）TreeSet

  1. class Solution {
  2.     public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
  3.         long ans = 0;
  4.         TreeSet<Integer> ts = new TreeSet();
  5.         for (int i = 0; i < nums1.length; i++) {
  6.             ts.add(nums1[i]);
  7.             ans += Math.abs(nums1[i] - nums2[i]);    // 将最小绝对差值进行累加
  8.         }
  9.         int pre = 0;
  10.         for (int i = 0; i < nums1.length; i++) {
  11.             int temp = Math.abs(nums1[i] - nums2[i]);
  12.             Integer floor = ts.floor(nums2[i]);        // 找到小于等于nums2[i]的数
  13.             Integer ceiling = ts.ceiling(nums2[i]);    // 找到大于等于nums2[i]的数
  14.             int newMargin = ((floor == null)? Integer.MAX_VALUE : (nums2[i] - floor));
  15.             newMargin = Math.min(newMargin, ((ceiling == null)? newMargin : (ceiling - nums2[i])));
  16.             pre = Math.max(pre, Math.abs(temp - newMargin));    // 记录改变绝对差值的最大改变量
  17.         }
  18.         return (int)((ans - pre)%1000000007);
  19.     }
  20. }

时间复杂度为O(nlogn)，空间复杂度为O(n)，但由于每次循环都有两次寻找nums1中的数，这部分可以自己写二分查找来实现一次查找，找到两个数