05 August 2008
给定两个长度为 n 的正整数数组 nums1 和 nums2。
| 数组 nums1 和 nums2 的绝对和差定义为 | nums1[i] - nums2[i] | 的和对于每个 0 <= i < n（0 索引）。 |
最多可以将 nums1 的一个元素替换为 nums1 中的任何其他元素，以最小化绝对总和差异。
返回数组 nums1 中最多替换一个元素后的最小绝对和差。由于答案可能很大，将其取模 109 + 7 返回。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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.
这是一道二分陈题，具体做法如下：
我们在进行处理前，先对 nums1 进行拷贝并排序，得到 sorted 数组。
然后 在遍历 nums1 和 nums2 计算总的差值 sum 时，通过对 sorted 进行二分查找，找到最合适替换 nums[i] 的值。
具体的，当我们处理到第 i 位时，假设该位的原差值为 x = abs(nums1[i] - nums2[i])，然后从 sorted 数组中通过二分找到最接近 nums2[i] 的值，计算一个新的差值 nd（注意要检查分割点与分割点的下一位），如果满足 nd < x 说明存在一个替换方案使得差值变小，我们使用变量 max 记下来这个替换方案所带来的变化，并不断更新 max。
当整个数组被处理完，max 存储着最优方案对应的差值变化，此时 sum - max 即是答案。
时间复杂度：对 sorted 进行拷贝并排序的复杂度为 O(nlogn)；遍历处理数组时会一边统计，一边尝试二分，找最合适的替换数值，复杂度为 O(nlogn)。整体复杂度为 O(nlogn)
空间复杂度：使用 sorted 数组需要 O(n) 的空间复杂度，同时排序过程中会使用 O(logn) 的空间复杂度；整体复杂度为 O(n+logn)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
int mod = (int)1e9+7;
public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
int n = nums1.length;
int[] sorted = nums1.clone();
Arrays.sort(sorted);
long sum = 0, max = 0;
for (int i = 0; i < n; i++) {
int a = nums1[i], b = nums2[i];
if (a == b) continue;
int x = Math.abs(a - b);
sum += x;
int left = 0, right = n - 1;
while (left < right) {
int mid = left + right + 1 >> 1;
if (sorted[mid] <= b) left = mid;
else right = mid - 1;
}
int nd = Math.abs(sorted[right] - b);
if (right + 1 < n) nd = Math.min(nd, Math.abs(sorted[right + 1] - b));
if (nd < x) max = Math.max(max, x - nd);
}
return (int)((sum - max) % mod);
}
}