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

题目大意

给你两个正整数数组 nums1 和 nums2 ，数组的长度都是 n 。数组 nums1 和 nums2 的绝对差值和定义为所有 |nums1[i] - nums2[i]|（0 <= i < n）的总和（下标从 0 开始）。你可以选用 nums1 中的任意一个元素来替换 nums1 中的至多一个元素，以最小化绝对差值和。在替换数组 nums1 中最多一个元素之后，返回最小绝对差值和。因为答案可能很大，所以需要对 10^9 + 7 取余后返回。

解题思路

如果不改变任何元素，绝对差值和为

$$\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。

代码

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
}

Uh oh!

pFad - (p)hone/(F)rame/(a)nonymizer/(d)eclutterfier! Saves Data!