1818. 绝对差值和 力扣(中等) 二分+排序 lower_bound(vector.begin(),..)

给你两个正整数数组 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;
    }
};

 

上一篇:【每日Leetcode-第四天】寻找两个正序数组的中位数


下一篇:如何快速合并两个有序数组?