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 oneelement in the array nums1
. Since the answer may be large, return it modulo 109 + 7
.
|x|
is defined as:
x
ifx >= 0
, or-x
ifx < 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
Solution: Binary Search
Greedy won’t work, e.g. finding the max diff pair and replace it. Counter example:
nums1 = [7, 5], nums2 = [1, -2]
pair1 = abs(7 – 1) = 6
pair2 = abs(5 – (-2)) = 7
If we replace 5 with 7, we got pair2′ = abs(7 – (-2)) = 9 > 7.
Every pair of numbers can be the candidate, we just need to find the closest number for each nums2[i].
Time complexity: O(nlogn)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution { public: int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) { constexpr int kMod = 1e9 + 7; const int n = nums1.size(); long ans = 0; int gain = 0; set<int> s(begin(nums1), end(nums1)); for (int i = 0; i < n; ++i) { const int diff = abs(nums1[i] - nums2[i]); ans += diff; if (diff <= gain) continue; auto it = s.lower_bound(nums2[i]); if (it != s.end()) gain = max(gain, diff - abs(*it - nums2[i])); if (it != s.begin()) gain = max(gain, diff - abs(*prev(it) - nums2[i])); } return (ans - gain) % kMod; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment