leetcode 1300 转变数组后最接近目标值的数组和

题目

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-of-mutated-array-closest-to-target
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

1.二分查找（二分答案）
找到第一个sum>target 的 阈值， 再与上一个（sum< target）的值比较，谁更接近target。即可。

const findBestValue = function (arr, target) {
    // 二分法
    let l = 0, r = Math.max(...arr)
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        if (calSum(mid, arr) < target) {
            l = mid + 1
        } else {
            r = mid
        }
    }
    if (calSum(l, arr) - target < target - calSum(l - 1, arr)) {
        return l
    } else {
        return --l
    }
}
const calSum = (x, arr) => {
    let sum = 0
    for (let v of arr) {
        sum += Math.min(x, v)
    }
    return sum
}

2.平均值
O（nlogn）
需要排序，然后通过平均值，依次网上找，知道找到第一个sum>target的值，再与前一个值比较即可。

// arr.sort((a, b) => a - b)

    // const n = arr.length
    // let mean = Math.floor(target / n)
    // let sum = 0
    // const res = []
    // while (sum < target) {
    //     if (mean >= arr[arr.length - 1]) {
    //         return mean
    //     }
    //     const temp = JSON.parse(JSON.stringify(arr))
    //     for (let i in temp) {
    //         if (temp[i] > mean) {
    //             temp[i] = mean
    //         }
    //     }
    //     sum = eval(temp.join('+'))
    //     res.push(sum)
    //     mean++
    // }
    // if (res[res.length - 1] - target < target - res[res.length - 2]) {
    //     return --mean
    // } else {
    //     return mean - 2
    // }