力扣_1300. 转变数组后最接近目标值的数组和

0
11

题目描述:
给你一个整数数组 arr 和一个目标值 target ,请你返回一个整数 value ,使得将数组中所有大于 value 的值变成 value 后,数组的和最接近 target (最接近表示两者之差的绝对值最小)。
如果有多种使得和最接近 target 的方案,请你返回这些整数中的最小值。
请注意,答案不一定是 arr 中的数字。

提示中给的是二分法,而二分法官方解答已经很详细了,下面是我的解体思路

首先,这道题的根本目的是在数组中切一刀。那么具体在哪切一刀呢?

根据题意我们可以确定value的最小值是1,最大值可以取到arr数组的最大值。那么最暴力的方法当然是直接再value的取值范围里采用循环遍历,找出value的值。当然,这样做的时间成本太大了,力扣是不会给你分的(我已经试过了)。

为了清晰的描述我的思路,这里先举个栗子。

为了方便,我这里直接给出一个已经排列好的数组。(数组的排列可以直接使用sort()函数)

arr[]={7,9,12,17,19,25}  target=80

这里的数组大小是6,要让它的和接近80,那么也就是说这6个数的平均值要接近13.33(80/6),也就是说,此数组不可能在12的前面切一刀

若在12后面17前面切一刀,新数组arr[7,9,12,x,x,x],为了使数组和更接近target:

那么 80-7-9-12=52  x=52/3=17.33<17.5,

所以X最合适的值就是17,即value=17

代码如下:

classSolution{
public:
intfindBestValue(vector<int>&arr,inttarget){
sort(arr.begin(),arr.end());  //将数组从小到大排列
intpre=0,rest=arr.size();  //将数组切成两段 pre表示前一段数字的和,rest表述后一段数字的个数
doubletemp;  //存储平均数x的值
for(inti=0;i<arr.size();i++){
temp=double(target-pre)/rest;  //循环遍历
if(temp<=arr[i]){
if(temp-int(temp)>0.5)returnint(temp)+1;  //若是平均值小于数组内的最小值,那么value就等于四舍五入后的平均值
returnint(temp);
}
pre+=arr[i];
rest–;
}
returnarr[arr.size()-1];  //若是平均值大于数组内的最大值,那么value就等于数组内的最大值
}
};

如果有什么问题,欢迎大家指正!

<

发布回复

请输入评论!
请输入你的名字