给你两个正整数数组 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
题源:https://leetcode-cn.com/problems/minimum-absolute-sum-difference/
学习要点:
auto ii=lower_bound(vector.begin(),vector.end((),num); //返回迭代器 int ii=lower_bound(vector.begin(),vector.end(),num)-vector.begin(); // 返回下标 auto ii=mp.lower_bound(keynum); // 返回迭代器
代码:
class Solution { public: int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) { vector<int> a; a.assign(nums1.begin(),nums1.end()); sort(a.begin(),a.end()); long long mod=1e9+7; long long sum=0; for(int i=0;i<nums1.size();i++) sum=sum+abs(nums1[i]-nums2[i]); if(sum==0) return sum; long long res=sum; for(int i=0;i<nums2.size();i++) { auto id=lower_bound(a.begin(),a.end(),nums2[i]); //得到迭代器 // int j = lower_bound(a.begin(), a.end(), nums2[i]) - rec.begin(); //得到下标 if(id!=a.end()) //有可能没有找到 res=min(res,sum -abs(nums1[i]-nums2[i]) +abs(*id-nums2[i]) ); if (id>a.begin()) //有可能在开头,不能倒退 { id--; res=min(res,sum -abs(nums1[i]-nums2[i]) +abs(*id-nums2[i])); } } return res%mod; } };