题目地址
个人博客地址

题目描述

给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近 target （最接近表示两者之差的绝对值最小）。

如果有多种使得和最接近 target 的方案，请你返回这些整数中的最小值。

请注意，答案不一定是 arr 中的数字。

示例 1：

输入：arr = [4,9,3], target = 10
输出：3
解释：当选择 value 为 3 时，数组会变成 [3, 3, 3]，和为 9 ，这是最接近 target 的方案。

示例 2：

输入：arr = [2,3,5], target = 10
输出：5
示例 3：

输入：arr = [60864,25176,27249,21296,20204], target = 56803
输出：11361

解法

java

public class Solution {
    public int findBestValue(int[] arr, int target) {
        int sum=0,maxNum=arr[0];
        for (int a: arr) {
            if(a>maxNum) maxNum=a;
            sum+=a;
        }
        if(sum<=target) return maxNum;
        int left=0;
        int right=maxNum;
        while (left<=right){
            int mid=(left+right)>>1;
            int temp= getSum(arr,mid);
            if(temp-target==0) return mid;
            else if(temp<target) left=mid+1;
            else right=mid-1;
        }
  if(Math.abs(get_sum(arr,left)-target)<Math.abs(get_sum(arr,right)-target)) return left;
        else 
            return right;
    }
    public int getSum(int [] arr, int value){
        int sum=0;
        for (int a: arr) {
            if(a>value) sum+=value;
            else sum+=a;
        }
        return sum;
    }
}

解题思路

二分法

总结题目的要求。
如果原数组的和SUM小于等于target，之间返回数组的最大值便可以了，因为无论怎么调整数组的值，都不会出现和大于target。

 int sum=0,maxNum=arr[0];
        for (int a: arr) {
            if(a>maxNum) maxNum=a;
            sum+=a;
        }
        if(sum<=target) return maxNum;

如果原数组的和大于target，这里我们便需要在0~最大值maxNum中，需要一个value使得数组的和SUM最接近 target。
1.先实现获取sum的方法

  public int getSum(int [] arr, int value){
        int sum=0;
        //题目要求所有大于 value 的值变成 value，计算时取value值便可以了
        for (int a: arr) {
            if(a>value) sum+=value;
            else sum+=a;
        }
        return sum;
    }

2.寻找value
使用二分法，需要一个value，使得

        int left=0;
        int right=maxNum;
        while (left<=right){
            int mid=(left+right)>>1;
            int temp= getSum(arr,mid);
            if(temp-target==0) return mid;
            //取得一个和接近target的值
            else if(temp<target) left=mid+1;
            else right=mid-1;
        }

如果正好，mid的计算的值等于target。我们返回mid，不满足时，退出的条件为left>right，此时value取值left是一个数组和sum(arr)大于并且接近target的值，value取值right，是一个数组和sum(arr)小于并且接近target的值

  if(Math.abs(get_sum(arr,left)-target)<Math.abs(get_sum(arr,right)-target)) return left;
 else 
 return right;