[排序和二分] 绝对差值和

2024-09-01 08:12
文章标签 二分 排序 绝对 差值

本文主要是介绍[排序和二分] 绝对差值和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

提示:

  • n == nums1.length
  • n == nums2.length
  • 1 <= n <= 105
  • 1 <= nums1[i], nums2[i] <= 105

解题分析

这题的话需要我们耐心地去分析,首先,我们很容易想到枚举的方法,总共有n^2种情况,我们可以全部遍历然后找到绝对差值和最小的那种情况,最后输出答案即可,不过这种方法显然很容易超时。那有没有更好的方法呢?比如说排序或者二分法?当然可以。我们不妨取出一个局部去观察,首先,对于任意一个位置的i,abs(nums1[i]-nums2[i])就是这个位置对于答案的贡献,如果我们用j位置的数去置换掉i位置(0<=i,j<n,其中n为nums1数组的长度),那么这个位置的贡献就变成了abs(nums1[j]-nums2[i])。两次的差值为maxn = abs(nums1[i]-nums2[i]) - abs(nums1[j]-nums2[i])。那么最终的答案就会变成sum - maxn。我们想让sum最小,只需让maxn最大即可。我们回到表达式中,可以比较清楚地发现,一旦i确定了,我们只需要去寻找一个j,就可以确定这个值,j应该怎么取呢?其实也比较容易发现,我们只需要让nums1[j]接近nums2[i]即可,也就是说我们二分查找一下nums1数组中和nums2[i]接近的两个数(可能更小,也可能更大),然后比较哪个更小即可。这里推荐使用lower_bound,可以比较快地返回一个迭代器,迭代器指向的是大于等于nums2[i]的一个数的位置,由于vector的内存是连续分布的,所以我们可以作减法得到一个下标的位置。

代码实现

class Solution {
public:static constexpr int mod = 1'000'000'007;int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {vector<int> rec(nums1);sort(rec.begin(),rec.end());int sum = 0, maxn = 0;int n = nums1.size();for(int i = 0 ; i < n ; i++){int diff = abs(nums1[i] - nums2[i]);sum = (sum + diff) % mod;int j = lower_bound(rec.begin(),rec.end(),nums2[i]) - rec.begin();if(j < n){maxn = max(maxn, diff - (rec[j] - nums2[i]));}if(j > 0){maxn = max(maxn, diff - (nums2[i] - rec[j-1]));}}return (sum - maxn + mod) % mod;}
};

这篇关于[排序和二分] 绝对差值和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1126402

相关文章

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

poj 3104 二分答案

题意: n件湿度为num的衣服,每秒钟自己可以蒸发掉1个湿度。 然而如果使用了暖炉,每秒可以烧掉k个湿度,但不计算蒸发了。 现在问这么多的衣服,怎么烧事件最短。 解析: 二分答案咯。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <c

poj 3258 二分最小值最大

题意: 有一些石头排成一条线,第一个和最后一个不能去掉。 其余的共可以去掉m块,要使去掉后石头间距的最小值最大。 解析: 二分石头,最小值最大。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c

poj 2594 二分图最大独立集

题意: 求一张图的最大独立集,这题不同的地方在于,间接相邻的点也可以有一条边,所以用floyd来把间接相邻的边也连起来。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <sta

poj 3692 二分图最大独立集

题意: 幼儿园里,有G个女生和B个男生。 他们中间有女生和女生认识,男生男生认识,也有男生和女生认识的。 现在要选出一些人,使得这里面的人都认识,问最多能选多少人。 解析: 反过来建边,将不认识的男生和女生相连,然后求一个二分图的最大独立集就行了。 下图很直观: 点击打开链接 原图: 现图: 、 代码: #pragma comment(