一、题目

二、分析与解答

分析：i 处对答案的贡献为 | nums1[i] - nums2[i] | ，若用元素 nums1[j] 替换 nums1[i] 那么贡献变为 | nums1[j] - nums2[i] |。两者的差值尽可能大 | nums1[i] - nums2[i] | - | nums1[j] - nums2[i] |。
检查每一个 i 对应的差值，当 i 确定时，前半部分大小确定；而后半部分取决于 j 的选择，因此利用二分查找在 nums1 中查找 nums1[j] 尽可能的接近 nums1[i]。

class Solution {
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        final int MOD = 1000000007;
        int n = nums1.length;
        int[] rec = new int[n];
        System.arraycopy(nums1, 0, rec, 0, n);
        Arrays.sort(rec);
        int sum = 0, maxn = 0;
        for (int i = 0; i < n; i++) {
            int diff = Math.abs(nums1[i] - nums2[i]);
            sum = (sum + diff) % MOD;
            int j = binarySearch(rec, nums2[i]);
            if (j < n) {
                maxn = Math.max(maxn, diff - (rec[j] - nums2[i]));
            }
            if (j > 0) {
                maxn = Math.max(maxn, diff - (nums2[i] - rec[j - 1]));
            }
        }
        return (sum - maxn + MOD) % MOD;
    }
    public int binarySearch(int[] rec, int target) {
        int low = 0, high = rec.length - 1;
        if (rec[high] < target) {
            return high + 1;
        }
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (rec[mid] < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}