小旭讲解 LeetCode 1818. Minimum Absolute Sum Difference
小旭讲解 LeetCode 1818. Minimum Absolute Sum Difference

视频讲解

题目^{[1]}

LeetCode 1818. Minimum Absolute Sum Difference
力扣 1818. 绝对差值和

思路 – 二分搜索

题目需要求得 sum = |nums1[i] - nums2[i]| 的最大值,且限定只能更改 nums1 中的某一个值,且可以更改的数值范围取决于 nums1 中的值的情况。

比较直接的思路,既然想求得 sum 的最大值且只能更改一项,那么必定要选择一项,其更改前与后的值差值最大化,也就意味着 sum 可以减少的值最大化,即在更改 nums1 的某一个值后,sum 可以最小化。

难点在于,如何确定某一位 nums1 要改成什么值?比较容易想到可以改成较为和原值接近的值,那么会满足上一段落的要求。在查找时,可以考虑将 nums1 排成有序数组,进行二分查找,此处为本地的灵魂所在。

可以使用 lower_bound 进行二分查找,在这里曾经总结过 lower_bound 与 upper_bound 的使用和区别。

    // binary search m >= t, 第一个大于等于 t 的位置
    // binary search m <= t, 最后一个小于等于 t 的位置
    // 升序数组, lower_bound, less 第一个 >= t 的位置
    // 降序数组, lower_bound, greater 第一个 <= t 的位置
    // 升序数组, upper_bound, less 第一个 > t 的位置
    // 降序数组, upper_bound, greater 第一个 < t 的位置
    low=std::lower_bound (v.begin(), v.end(), 20, greater());
    up= std::upper_bound (v.begin(), v.end(), 20, greater());

代码

class Solution {
public:
    int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
        int sum=0,mod=1e9+7,maxv=0;
        for (int i=0;i<nums1.size();++i) {
            sum += abs(nums2[i]-nums1[i]);
            sum %= mod;
        }
        vector<int> cp(nums1);
        sort(cp.begin(),cp.end()); // 升序
        for (int i=0;i<nums1.size();++i) {
            int v=nums2[i];
            // *it >= v
            auto it = lower_bound(cp.begin(), cp.end(), v);
            if (it != cp.end()) maxv = max(maxv, abs(nums2[i]-nums1[i]) - abs(*it - nums2[i]));
            if (it != cp.begin()) maxv = max(maxv, abs(nums2[i]-nums1[i]) - abs(*(--it) - nums2[i]));
        }
        return (sum - maxv + mod)%mod;
    }
};

复杂度分析

时间复杂度:O(NlogN)
空间复杂度:O(N)

参考

[1]. LeetCode 原题. https://leetcode.com/problems/minimum-absolute-sum-difference/
[2]. Github huxiaoxu2019/algorithm. https://github.com/huxiaoxu2019/algorithm/blob/master/basic-algorithm/sort/lower-bound.cpp#L12

欢迎分享,引用。若转载,请联系我,谢谢配合。
本文地址:https://qoogle.top/xiaoxu-tutorial-leetcode-1818-minimum-absolute-sum-difference/
0 0 vote
Article Rating
Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments