算法-二分查找-转变数组后最接近目标值的数组和

ゝ一世哀愁。 2023-02-17 13:26 21阅读 0赞

# 算法-二分查找-转变数组后最接近目标值的数组和 #

# 1 题目概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/sum-of-mutated-array-closest-to-target/

## 1.2 题目描述 ##

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

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

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

# 2 遍历求余法 #

## 2.1 思路 ##

将数组排序。

每次都求平均数avg，直到`avg > arr[i]`说明不能用平均数替换数组中下一个数。

这个时候还需要判断`(avg+1) * 剩余项`和remain的差值 是否小于 `avg * 剩余项`和remain的差值，如果是就取avg+1作为结果。

## 2.2 代码 ##

class Solution { 
        public int findBestValue(int[] arr, int target) { 
            if(arr == null || arr.length == 0){ 
                return 0;
            }
            int remain = target;
            
            int avg = target / arr.length;
            if(((avg + 1) * arr.length - target) < (target - avg * arr.length)){ 
                avg++;
            }
    
            if(avg * arr.length == target){ 
                return avg;
            }
    
            Arrays.sort(arr);
            int i = 0;
            int newL = 0;
            while(avg > arr[i]){ 
                remain -= arr[i];
                i++;
                if(i == arr.length){ 
                    return arr[arr.length - 1];
                }
                newL = arr.length - i;
                avg = remain / newL;
                if(((avg + 1) * newL - remain) < (remain - avg * newL)){ 
                    avg++;
                }
            }
            return avg;
        }
    }

## 2.3 时间复杂度 ##

![在这里插入图片描述][20200614122308422.png]  
O(N)

## 2.4 空间复杂度 ##

O(1)

# 3 二分查找 #

## 3.1 思路 ##

## 3.2 代码 ##

## 3.3 时间复杂度 ##

## 3.4 空间复杂度 ##

[20200614122308422.png]: https://img-blog.csdnimg.cn/20200614122308422.png