You are given two positive integer arrays nums1 and nums2, both of length N.

The absolute difference between the array nums1 and nums2 and defined as all | nums1 [I] – nums2 [I] | (0 < = I < n) the sum of (subscript starting from 0).

You can replace at most one element of nums1 with any element of nums1 to minimize the absolute sum.

After replacing at most one element in the array nums1, returns the sum of the minimum absolute differences. Because the answer may be large, you need to mod 109 + 7 and return.

| | x is defined as:

  • If x is greater than or equal to 0 and the value is x,
  • If x <= 0, the value is -x
Example 1: input: nums1 = [1,7,5], nums2 = [2,3,5] output: 3 explanation: there are two possible optimal solutions: - replace the second element with the first element: [1,7,5] => [1,1,5], or - replace the second element with the third element: ,5,5,7,5 [1] = > [1] the absolute difference between the two plans and are | 1-2 | + 1-3 (| | and | | 5-3) + | | = 5 ‑ 3 example 2: input: Nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10] Example 3: input: nums1 = [1,10,4,4,2,7], nums2 = [9,3,5,1,7,4] output: 20 explanation: replace the first element with the second element: ,10,4,4,2,7,10,4,4,2,7 [1] = > [10] and absolute difference value for 10-9 + | | | 3 | + 10 - | 4-5 + | | | | 4-1 + 2-7 + | | | 7-4 = 20Copy the code

Their thinking

  • The absolute difference value can be seen as consisting of nums1[I] and NUMs2 [I], so we need to deal with n such pairs this time.
  • For each nums2[I], we can quickly find the element closest to nums2[I] in the nums1 array. This element is the element that can replace nums1[I]. By comparing the difference of the original nums1[I] and nums2[I] with the difference after the replacement, we can quickly find the element closest to nums2[I]. The difference is the sum of the absolute differences, and the biggest one is the one that minimizes the sum of the absolute differences.

code

class Solution {
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
int mod=1000000007;long dif = 0;
        int n = nums1.length,  max = 0, maxi = -1;
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int abs = Math.abs(nums1[i] - nums2[i]);
            if(abs ! =0) {
                list.add(new int[]{nums2[i], abs});
            }
            dif += abs;
        }
        Arrays.sort(nums1);
        int gap=0;
        for (int i=0; i<list.size(); i++) {int abs=100001;
            int r = bs(nums1, list.get(i)[0]),l=r-1;
            if(r<n)
                abs=Math.min(abs,Math.abs(nums1[r]-list.get(i)[0]));
            if(l>=0)
                abs=Math.min(abs,Math.abs(nums1[l]-list.get(i)[0]));
            gap=(Math.max(gap,list.get(i)[1]-abs));
        }
        return (int)((dif-gap)%mod);
    }
    public int bs(int[] nums1,int tar ){

        int l=0,r=nums1.length-1;
        while (l<=r)
        {
            int mid=(r-l)/2+l;
            if(nums1[mid]>=tar)
                r=mid-1;
            else l=mid+1;
        }
        returnl; }}Copy the code