LeetCode力扣 1300题：转变数组后最接近目标值的数组和（二分查找）

Myth丶恋晨 2023-02-17 15:52 11阅读 0赞

题目：

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

> 提示：  
> 1 <= arr.length <= 10^4  
> 1 <= arr\[i\], target <= 10^5

### 分析 ###

很容易想到二分法。让大于 value 的都变成 value ，得到的总和来和 target 进行比较，可能大于、可能小于，最后取整数结果。

1.  结果最小是 0 ，（有很多情况比如arr=\[1,1,1,1\],target=1）；
2.  结果最大是 **arr 数组的最大值**，也就是不改变原数组。此时结果再大，也改变不了原数组加和 和 target 的关系，所以求最小的值就是 arr 的最大值。

class Solution {
        
        public int findBestValue(int[] arr, int target) {
        
            int max=0;
            int min=0;
            for(int num:arr){
        
                max=Math.max(max,num);
            }
    
            //开始二分查找对于每一个方案，得到的数组和的结果和 target 的距离，并更新
            while(min<max){
        
                int mid=min+(max-min)/2;
                int temp=count(arr,mid);
                if(temp<target){
        
                    min=mid+1;
                }else{
        
                    max=mid;
                }
            }
            int sum1=count(arr,min-1);
            int sum2=count(arr,min);
    
            return target-sum1>sum2-target? min:min-1;
        }
    
        //对于每一个方案 mid 值，计算总共的数组加和
        public int count(int[] arr, int line){
        
            int total=0;
            for(int num: arr){
        
                if(num>line){
        
                    total+=line;
                }else{
        
                    total+=num;
                }
            }
            return total;
        }
    }

这个代码改了很久，二分的时候开始在过程中是这样的：

while(min<max){
        
                int mid=min+(max-min)/2;
                int temp=count(arr,mid);
                if(temp<target){
        
                    min=mid+1;
                }else{
        
                    max=mid-1;
                }
            }

然后最后直接返回了 min ，结果有很多的值是和正确答案差 1.

思考了一下发现，因为这个过程里面，**无法确定二分的最后一步是执行的 mid+1 还是 mid-1。**

*  如果是在 min=4，max=5的时候，判断了一次，二分结束max=4，此时min=4；
 *  如果是在 min=4，max=5的时候，判断了一次，二分结束min=5，此时返回min=5。

这样我们返回的结果可能是错的，需要比较到底是 4 还是 5 带给数组的加和离 target 更近一些。

如果是二分查找比较普通的应用，判断结束的时候一般会返回一个绝对的正确答案，但是这个题目好像没有办法，哪怕最终的结果一定是 min 和 max 这两个边界相差为 1 ，组成加和之后，扩大的范围决定哪一个是正确答案是没法确定的。

因此现在为止，认为二分跳出之后只能通过再次比较：

int sum1=count(arr,min-1);
            int sum2=count(arr,min);
    
            return target-sum1>sum2-target? min:min-1;

来得到正确的结果。