[LeetCode] 1818. Minimum Absolute Sum Difference

[frdmu]

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

The absolute sum difference of arrays nums1 and nums2 is defined as the sum of |nums1[i] - nums2[i]| for each 0 <= i < n (0-indexed).

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

Return the minimum absolute sum difference after replacing at most one element in the array nums1. Since the answer may be large, return it modulo 109 + 7.

|x| is defined as:

• x if x >= 0, or
• -x if x < 0.

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: [1,7,5] => [1,1,5], or
- Replace the second element with the third: [1,7,5] => [1,5,5].
Both will yield an absolute sum difference of |1-2| + (|1-3| or |5-3|) + |5-5| = 3.

Example 2:

Input: nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10]
Output: 0
Explanation: nums1 is equal to nums2 so no replacement is needed. This will result in an 
absolute sum difference of 0.

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: [1,10,4,4,2,7] => [10,10,4,4,2,7].
This yields an absolute sum difference of |10-9| + |10-3| + |4-5| + |4-1| + |2-7| + |7-4| = 20

Constraints:

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

 
 
 
思路能根据提示想到，提示中有二分法，而且题目中有两个数组，这种题目的大致思路一般就是将其中一个数组排序，再把另一个数组中的元素当做target，在已排序的数组中用二分法进行查找。
试了一下示例，这道题就是这个思路，二分法查找的是离target最近的两个元素。代码如下：

class Solution {
public:
    int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
        int res = INT_MAX;
        int n = nums1.size();
        int mod = 1e9 + 7;
        vector<int> vec(nums1); 
        int sum = 0;
        
        sort(vec.begin(), vec.end());
        for (int i = 0; i < n; i++) {
            sum = sum % mod + abs(nums1[i] - nums2[i]) % mod;   
        } 
        for (int i = 0; i < n; i++) {
            if (nums2[i] != nums1[i]) {
                
                int left = 0, right = n;
                while (left < right) {
                    int mid = left + (right - left) / 2;
                    if (vec[mid] <= nums2[i]) left = mid + 1;
                    else right = mid;
                }
                int upper = INT_MAX, lower = INT_MAX;
                if (right >= 1 && right < n) {
                    upper = vec[right];
                    lower = vec[right-1];
                } 
                if (right <= 0) {
                    upper = vec[0];
                    lower = vec[0];
                }
                if (right >= n) {
                    upper = vec[n-1];
                    lower = vec[n-1];
                }
                
                int replace = abs(lower-nums2[i]) > abs(upper-nums2[i]) ? upper : lower;
                if (replace != nums1[i]) {
                    int sub = abs(nums1[i]-nums2[i]) - abs(replace-nums2[i]);
                    res = min(sum-sub+mod, res);  //这里的+mod没弄明白，看了题解加上的
                } 
            } 
        }
        
        return res == INT_MAX ? 0 : res%mod; 
    }
};