网站代码优化所有标签,建筑建设工程信息服务平台,深圳影视传媒公司有哪些,高端品销售网站给你两个正整数数组 nums1 和 nums2 #xff0c;数组的长度都是 n 。
数组 nums1 和 nums2 的 绝对差值和 定义为所有 |nums1[i] - nums2[i]|#xff08;0 i n#xff09;的 总和#xff08;下标从 0 开始#xff09;。
你可以选用 nums1 中的 任意一个 元素来… 给你两个正整数数组 nums1 和 nums2 数组的长度都是 n 。
数组 nums1 和 nums2 的 绝对差值和 定义为所有 |nums1[i] - nums2[i]|0 i n的 总和下标从 0 开始。
你可以选用 nums1 中的 任意一个 元素来替换 nums1 中的 至多 一个元素以 最小化 绝对差值和。
在替换数组 nums1 中最多一个元素 之后 返回最小绝对差值和。因为答案可能很大所以需要对 109 7 取余 后返回。
|x| 定义为
如果 x 0 值为 x 如果 x 0 值为 -x 示例 1输入nums1 [1,7,5], nums2 [2,3,5]
输出3
解释有两种可能的最优方案
- 将第二个元素替换为第一个元素[1,7,5] [1,1,5] 或者
- 将第二个元素替换为第三个元素[1,7,5] [1,5,5]
两种方案的绝对差值和都是 |1-2| (|1-3| 或者 |5-3|) |5-5| 3
示例 2输入nums1 [2,4,6,8,10], nums2 [2,4,6,8,10]
输出0
解释nums1 和 nums2 相等所以不用替换元素。绝对差值和为 0
示例 3输入nums1 [1,10,4,4,2,7], nums2 [9,3,5,1,7,4]
输出20
解释将第一个元素替换为第二个元素[1,10,4,4,2,7] [10,10,4,4,2,7]
绝对差值和为 |10-9| |10-3| |4-5| |4-1| |2-7| |7-4| 20解题思路
绝对差值可以看为由nums1[i]、nums2[i]两个元素组成所以我们这次需要处理的就是n个这样的数对。对于每个nums2[i]我们使用二分法可以在nums1数组中快速找到最接近nums2[i]的元素这个元素就是可以替换nums1[i]的元素通过比较原nums1[i]、nums2[i]的差值和替换以后的差值这个差值就是对于绝对差值和的减益选出最大的那个减益就是使得绝对差值和最小化的方案。
代码
class Solution {public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
int mod1000000007;long dif 0;int n nums1.length, max 0, maxi -1;Listint[] list new ArrayList();for (int i 0; i n; i) {int abs Math.abs(nums1[i] - nums2[i]);if (abs ! 0) {list.add(new int[]{nums2[i], abs});}dif abs;}Arrays.sort(nums1);int gap0;for (int i0;ilist.size();i){int abs100001;int r bs(nums1, list.get(i)[0]),lr-1;if(rn)absMath.min(abs,Math.abs(nums1[r]-list.get(i)[0]));if(l0)absMath.min(abs,Math.abs(nums1[l]-list.get(i)[0]));gap(Math.max(gap,list.get(i)[1]-abs));}return (int)((dif-gap)%mod);}public int bs(int[] nums1,int tar ){int l0,rnums1.length-1;while (lr){int mid(r-l)/2l;if(nums1[mid]tar)rmid-1;else lmid1;}return l;}
}
