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

谁践踏了优雅 2023-02-17 15:57 12阅读 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
    解释：当选择 value 为 5 时，数组会变成 [2,3,5]，2+3+5=10  ，这时两者相等，两者之差为0)。

示例 3：

输入：arr = [60864,25176,27249,21296,20204], target = 56803
    输出：11361
    解释：当选择 value 为 11361 时，[11361,11361,11361,11361,11361]，数组之和为56805，两者之差为2。

提示：

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

# 代码 #

public class Solution { 
    
        public int findBestValue(int[] arr, int target) { 
            int left = 0;
            int right = 0;
            // 注意：
            for (int num : arr) { 
                right = Math.max(right, num);
            }
    
            while (left < right) { 
                int mid = left + (right - left + 1) / 2;
                int sum = calculateSum(arr, mid);
                // 计算最后 1 个使得转变以后数组的和小于等于 target 的阈值 threshold
                if (sum > target) { 
                    // 大于等于的就不是解，threshold 太大了，下一轮搜索区间是 [left, mid - 1]
                    right = mid - 1;
                } else { 
                    // 下一轮搜索区间是 [mid, right]
                    left = mid;
                }
            }
    
            // 比较阈值线分别定在 left 和 left + 1 的时候与 target 的接近程度
            int sum1 = calculateSum(arr, left);
            int sum2 = calculateSum(arr, left + 1);
            // 注意：这里必须加绝对值，因为有可能出现 sum1 == sum2 < target 的情况
            if (Math.abs(target - sum1) <= Math.abs(sum2 - target)) { 
                return left;
            }
            return left + 1;
        }
    
        private int calculateSum(int[] arr, int threshold) { 
            int sum = 0;
            for (int num : arr) { 
                sum += Math.min(num, threshold);
            }
            return sum;
        }
    
        public static void main(String[] args) { 
            int[] arr = new int[]{ 2, 3, 5};
            int target = 11;
            Solution solution = new Solution();
            int res = solution.findBestValue(arr, target);
            System.out.println(res);
        }
    }

[来自liweiwei1419][liweiwei1419]

[liweiwei1419]: https://leetcode-cn.com/problems/sum-of-mutated-array-closest-to-target/solution/er-fen-cha-zhao-by-liweiwei1419-2/