题目分析

题目有一定的难度，如果想明白一个问题，则本题可以迎刃而解。下面给小伙伴们一些提示，其实本题就是在nums1中寻找与每个nums1元素对应的num2元素最接近的一个数。

二分查找

遍历num1所有索引，可以得到对应的num2元素，因此原本的绝对值之差为abs(nums1[i] - nums2[i])，如果将num1[i]换成与num2[i]最接近的一个数，那么绝对值之差就会最小，本题即寻找每一个索引对应的绝对值之差最小值。

我们可以新建一个数组，其中对nums1的元素进行排序，这样可以通过二分查找距离nums2[i]最近的元素，因为距离最近可以是大于nums2[i]的值，也可以是小于num2[i]的值，所以先找到大于等于nums[i]的最小值，然后找小于nums[i]的最大值即可。找到了距离nums2[i]最近的元素，我们判断该索引的绝对差变化了多少，原始的绝对差为abs(nums1[i] - nums2[i])，现在的绝对差为abs(find - nums2[i])，因此求abs(nums1[i] - nums2[i]) - abs(find - nums2[i])的最大值。

在每一步索引都计算绝对差，最后用总绝对差减去绝对差的变化量，即可求得替换后绝对差的最小值。

算法的时间复杂度为$O(nlog(n))$，空间复杂度为$O(n)$

下面是Java语言的题解

class Solution {
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        int mod = 1000000007;
        int length = nums1.length;
        int[] sortNum1 = Arrays.copyOf(nums1, length);
        Arrays.sort(sortNum1);
        int res = 0;
        int diff = 0;
        for (int i = 0; i < length; i++) {
            int cur = Math.abs(nums1[i] - nums2[i]);
            res = (res + cur) % mod;
            int left = 0, right = length - 1;
            while (left < right) {
                int mid = left + ((right - left) >> 1);
                if (sortNum1[mid] >= nums2[i]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            diff = Math.max(diff, cur - Math.abs(sortNum1[left] - nums2[i]));
            if (left > 0) { diff = Math.max(diff, cur - Math.abs(sortNum1[left - 1] - nums2[i])); }
        }
        return (res - diff + mod) % mod;
    }
}

刷题总结

本题是一个非常有趣的二分查找算法，希望小伙伴们能够举一反三多加练习。