题目描述:
给你一个整数数组 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

代码如下:

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

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

内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/pearli/p/13125067.html

你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!

相关课程