1818. Minimum Absolute Sum Difference

# 1818. Minimum Absolute Sum Difference#

## 题目 #

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 <= 10^5
• 1 <= nums1[i], nums2[i] <= 10^5

## 解题思路 #

• 如果不改变任何元素，绝对差值和为 $$\sum \left | nums1[i] - nums2[i] \right |$$ 。如果改变一个元素后，那么绝对差值和为 \begin{aligned}&\sum \left | nums1[i] - nums2[i] \right | - \left ( \left | nums1[i] - nums2[i] \right | - \left | nums1[j] - nums2[i] \right |\right )\\= &\sum \left | nums1[i] - nums2[i] \right | - \Delta \end{aligned}

题目要求返回最小绝对差值和，即求 $$\Delta$$ 的最大值。暴力枚举 nums1 和 nums2 中两两差值，找到 maxdiff，即 $$\Delta$$ 的最大值，此题得到解。

## 代码 #

package leetcode

func minAbsoluteSumDiff(nums1 []int, nums2 []int) int {
diff := 0
maxDiff := 0
for i, n2 := range nums2 {
d := abs(nums1[i] - n2)
diff += d
if maxDiff < d {
t := 100001
for _, n1 := range nums1 {
maxDiff = max(maxDiff, d-min(t, abs(n1-n2)))
}
}
}
return (diff - maxDiff) % (1e9 + 7)
}

func max(a, b int) int {
if a > b {
return a
}
return b
}

func abs(a int) int {
if a > 0 {
return a
}
return -a
}

func min(a, b int) int {
if a > b {
return b
}
return a
}


Apr 8, 2023