Leetcode 1818 absolute value, sorting, dichotomy, maximum value

1818. Absolute difference and

Medium difficulty 130 Switch to English to receive dynamic feedback

Here are two arrays of positive integers  nums1  and  nums2 , The length of the array is  n .

Array  nums1  and  nums2  Of   Absolute difference and   Defined as all  |nums1[i] - nums2[i]|（0 <= i < n） Of   The sum of the （ Subscript from 0 Start ）.

You can choose  nums1  Medium   Any one   Element to replace  nums1  Medium   at most   An element , With   To minimize the   Absolute difference and .

Replacing arrays  nums1  At most one element in   after  , Returns the minimum absolute difference and . Because the answer can be big , So you need to  109 + 7  Remainder   After the return .

|x|  Defined as ：

• If  x >= 0 , The value is  x , perhaps
• If  x <= 0 , The value is  -x

Example 1：

 Input ：nums1 = [1,7,5], nums2 = [2,3,5]
 Output ：3
 explain ： There are two possible optimal solutions ：
-  Replace the second element with the first ：[1,7,5] => [1,1,5] , perhaps 
-  Replace the second element with the third ：[1,7,5] => [1,5,5]
 The sum of absolute difference of the two schemes is  |1-2| + (|1-3|  perhaps  |5-3|) + |5-5| = 3

Example 2：

 Input ：nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10]
 Output ：0
 explain ：nums1  and  nums2  equal , So you don't have to replace elements . The sum of absolute difference is  0

Example 3：

 Input ：nums1 = [1,10,4,4,2,7], nums2 = [9,3,5,1,7,4]
 Output ：20
 explain ： Replace the first element with the second ：[1,10,4,4,2,7] => [10,10,4,4,2,7]
 The sum of absolute difference is  |10-9| + |10-3| + |4-5| + |4-1| + |2-7| + |7-4| = 20

Tips ：

• n == nums1.length
• n == nums2.length
• 1 <= n <= 105
• 1 <= nums1[i], nums2[i] <= 105

Pass times 27,976 Submit the number 74,953

This topic , The code came to mind after thinking for an hour , The answer to the question is ： Record an array of absolute values of difference diffnums, Then iterate through the array 2, Find if array 1 After replacing a number in , The absolute value produced corresponds to diffnums Do a bad job , Find the maximum difference , that will do , Finally, return to the changed sum .

The code is as follows ;

class Solution {
public:
    int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
        vector<int> diffnums(nums1.size(),0);
        long sum=0;
        for(int i=0;i<nums1.size();i++)
        {
            diffnums[i]=abs(nums1[i]-nums2[i]);
            sum+=diffnums[i];
            sum %= 1000000007;
        }
        sort(nums1.begin(),nums1.end());
        long maxvalue=0;
        for(int i=0;i<nums2.size();i++)
        {
            int pos=lower_bound(nums1.begin(),nums1.end(),nums2[i])-nums1.begin();
            if(pos<nums1.size())
            {
                maxvalue=max(maxvalue,(long)diffnums[i]-abs(nums1[pos]-nums2[i]));
            }
            if(pos>0)
            {
                maxvalue=max(maxvalue,(long)diffnums[i]-abs(nums1[pos-1]-nums2[i]));
            }
             maxvalue %= 1000000007;
        }
        return sum-maxvalue<0?sum-maxvalue+1000000007:sum-maxvalue;
    }
};

Execution results ：

adopt

According to the details

Add notes

Execution time ：168 ms, In all  C++  Defeated in submission 50.73% Users of

Memory consumption ：62.3 MB, In all  C++  Defeated in submission 80.46% Users of

Pass the test case ：51 / 51