Medium

题目描述

给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近 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 的元素都替换为 value 后，数组和最接近目标值 target。

思路分析

关键观察：当我们固定一个 value 时，数组的和是可以计算的。随着 value 的增大，数组和也会增大，这是一个单调递增的函数。因此我们可以使用二分搜索来找到最优解。

算法步骤：

  1. 确定搜索范围：value 的最小值是 0，最大值可以设为数组的最大值（因为超过最大值后数组和不再变化）
  2. 二分搜索：在搜索范围内二分查找，对于每个候选 value，计算对应的数组和
  3. 计算数组和：给定 value，遍历数组，如果元素大于 value 则用 value 替代，否则保持原值
  4. 选择最优解：比较当前 value 和 value+1 对应的数组和与目标的差距，选择更接近的那个

优化细节：

  • 可以先对数组排序，这样计算某个 value 对应的数组和时可以更高效
  • 排序后可以使用前缀和技术，快速计算小于等于 value 的元素和

代码实现

class Solution {
public:
    int findBestValue(vector<int>& arr, int target) {
        sort(arr.begin(), arr.end());
        int n = arr.size();
        
        auto getSum = [&](int value) -> long long {
            long long sum = 0;
            for (int x : arr) {
                sum += min(x, value);
            }
            return sum;
        };
        
        int left = 0, right = *max_element(arr.begin(), arr.end());
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (getSum(mid) < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        // 检查 left-1 和 left 哪个更接近目标
        long long sum1 = getSum(left - 1);
        long long sum2 = getSum(left);
        
        if (abs(sum1 - target) <= abs(sum2 - target)) {
            return left - 1;
        }
        return left;
    }
};

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        arr.sort()
        
        def get_sum(value):
            return sum(min(x, value) for x in arr)
        
        left, right = 0, max(arr)
        
        while left < right:
            mid = (left + right) // 2
            if get_sum(mid) < target:
                left = mid + 1
            else:
                right = mid
        
        # 检查 left-1 和 left 哪个更接近目标
        sum1 = get_sum(left - 1)
        sum2 = get_sum(left)
        
        if abs(sum1 - target) <= abs(sum2 - target):
            return left - 1
        return left

public class Solution {
    public int FindBestValue(int[] arr, int target) {
        Array.Sort(arr);
        
        long GetSum(int value) {
            long sum = 0;
            foreach (int x in arr) {
                sum += Math.Min(x, value);
            }
            return sum;
        }
        
        int left = 0, right = arr.Max();
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (GetSum(mid) < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        // 检查 left-1 和 left 哪个更接近目标
        long sum1 = GetSum(left - 1);
        long sum2 = GetSum(left);
        
        if (Math.Abs(sum1 - target) <= Math.Abs(sum2 - target)) {
            return left - 1;
        }
        return left;
    }
}

var findBestValue = function(arr, target) {
    arr.sort((a, b) => a - b);
    
    const getSum = (value) => {
        return arr.reduce((sum, x) => sum + Math.min(x, value), 0);
    };
    
    let left = 0, right = Math.max(...arr);
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (getSum(mid) < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    // 检查 left-1 和 left 哪个更接近目标
    const sum1 = getSum(left - 1);
    const sum2 = getSum(left);
    
    if (Math.abs(sum1 - target) <= Math.abs(sum2 - target)) {
        return left - 1;
    }
    return left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n log n + n log(max(arr)))，其中 n 是数组长度。排序需要 O(n log n)，二分搜索需要 O(log(max(arr))) 次，每次计算数组和需要 O(n)
空间复杂度O(1)，只使用了常数额外空间（不考虑排序的空间开销）