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

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

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

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

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

示例 1：

1
2
3

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

示例 2：

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

示例 3：

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

提示：

1 <= arr.length <= 10^4
1 <= arr[i], target <= 10^5

选择一个 value ，将整数数组 arr 中小于 value 的值保留，大于 value 的值变为 value，求修改后的数组的和，当数组的和最接近 target 是，value 就是我们需要找到的结果。显然，此题在数组有序时求比某一个 value 小的值时间复杂度更低，我们首先将数组排序，并生成前缀和数组，这样在 O(1)时间内就可求出数组中小于 value 的值的和，更进一步，已知数组的长度，可以求出修改后的数组的和。

value 的最小值为 1，最大值为数组 arr 的最大值，枚举每一个 value ，使用二分查找找出 value 在数组中的下标，求取修改后的数组和。

class Solution {
    public int findBestValue(int[] arr, int target) {
        //排序并生成前缀数组
        Arrays.sort(arr);
        int len = arr.length;
        int[] prefix = new int[len + 1];
        for(int i = 1; i <= len; ++i){
            prefix[i] = prefix[i - 1] + arr[i - 1];
        }
        
        int ans = 0, diff = target;
        //枚举每一个 value
        for(int i = 1; i <= arr[len - 1]; i++){
            //搜索数组中每个 value(i) 的下标
            int index = Arrays.binarySearch(arr, i);
            //未找到，将index 恢复为 i
            if(index < 0){
                index = - index - 1;
            }
            //计算修改后的数组和，并记录最佳结果
            int cur = prefix[index] + (len - index) * i;
            if(Math.abs(cur - target) < diff){
                ans = i;
                diff = Math.abs(cur - target);
            }
        }
        return ans;
    }
}

时间复杂度 O((N + C) logN)，其中 N 是数组 arr 的长度，C 是一个常数，为数组 arr 中的最大值。

空间复杂度 O(N)，前缀和数组使用 O(N) 的空间，排序需要 O(logN)的栈空间。

我们可以观察到，上述中的 value 从 1 到数组最大值 arr[len - 1]单调递增，所求出的修改后的数组和也是单调递增的，那么我们可以使用二分查找替代外层循环，来寻找最佳的 value值。

我们可以找出 value 使得数组的和最接近 target 且不大于 target，记为 value_lower，找出另一个 value 使得数组的和最接近 target 且大于 target，记为value_upper，最后的结果肯定是这两者中的一个。由于数组的和随着 value 的增大严格单调递增，value_lower 是最接近且不大于 target ，value_lower 是最接近且大于 target，所以 value_upper = value_lower + 1，所以只用一次二分查找来找到 value_lower即可。

class Solution {
    public int findBestValue(int[] arr, int target) {
        //计算前缀和
        Arrays.sort(arr);
        int len = arr.length;
        int[] prefix = new int[len + 1];
        for(int i = 1; i <= len; ++i){
            prefix[i] = prefix[i - 1] + arr[i - 1];
        }
        int l = 0, r = arr[len - 1], ans = -1;
        //二分查找寻找 value_lower
        while(l <= r){
            int mid = (l + r) / 2;
            int index = Arrays.binarySearch(arr, mid);
            if(index < 0){
                index = - index - 1;
            }
            int cur = prefix[index] + (len - index) * mid;
            if(cur <= target){
                ans = mid;
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
		//比较计算 value_lower 和 value_upper 修改后的数组和
        int lower = 0, upper = 0;
        for(int n : arr){
            lower += Math.min(n, ans);
            upper += Math.min(n, ans + 1);
        }
		//返回距离 target 最近的value值
        return Math.abs(lower - target) <= Math.abs(upper - target) ? ans : ans + 1;
    }

}

时间复杂度 O(N logN)，其中 N 是数组 arr 的长度。

空间复杂度 O(N)，前缀和数组使用 O(N) 的空间，排序需要 O(logN)的栈空间。