LeetCode.1300.Sum of Mutated Array Closest to Target 转变数组后最接近目标值的数组和

题目描述

1300 Sum of Mutated Array Closest to Target
https://leetcode-cn.com/problems/sum-of-mutated-array-closest-to-target/

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

---

解题过程

题意比较难理解，给定一个正整数数组，找一个数 value （不一定是数组中的值），使得把数组中所有大于 value 的值变为 value 后的总和最接近 target

value 值有上下界：
下界是 0，此时转换后的数组总和是 0
上界是数组元素最大值 max(arr)，此时数组无需转换，总和还是原始数组总和。

我们的目标是在 [0, max(arr)] 中找到一个值 value，使得转换后的数组总和最接近 target
如果有多个 value 值，比如 value1 使得转换后数组总和是 target-1，value2 使得转换后数组总和是 target+1，则取 value1, value2 中的最小值。

仔细分析这个转换过程，可以发现一个规律，value 值越小则转换后数组总和越小，value 值越大则转换后数组总和越大，因为 value 值越小越会使得原数组中更多的元素被更小的 value 替换，从而使得总和越小，value 值越大越少元素被替换。

用 mutatedSum(x) 表示把数组 arr 中所有大于 x 的值都变为 x 后的元素和，则
对于 0 <= x < y <= max(arr)，有 mutatedSum(x) < mutatedSum(y)，也就是 mutatedSum(x) 是关于 x 的单调递增函数。
所以我们可以使用二分法搜索 [0, max(arr)] 范围内的 value 值，来找到使得转换后数组总和最接近的 target 的 value。

有几点需要注意：
1、对于二分搜索中的每个 x 值，如何更快速的计算 mutatedSum(x) ？
我们可以先将原数组 arr 升序排序，然后就可以使用二分搜索在 O(logn) 复杂度内找到第一个大于等于 x 的值下标 xIndex，然后 mutatedSum 就等于 preSum(xIndex) + (arr.length - 1) * x，所以可以求出排序后 arr 数组的前缀和保存下来加快计算。

2、使用二分法求出 mutatedSum(x) < target 且最接近 target 的 value 后，还需要看下 value + 1 是否会是的 mutatedSum() 更小，并比较选取最终结果。

排序时间复杂度 O(nlogn)，外层二分搜索时间复杂度 O(logC)，其中 C 是数组最大值，内层二分搜索时间复杂度 O(logn)，总的时间复杂度 O(nlogn)
空间复杂度 O(n)

private static class SolutionV202006 {
    public int findBestValue(int[] arr, int target) {
        // 升序排序
        Arrays.sort(arr);
        // 数组 arr 的前缀和， preSum[i] 表示下标 i 之前所有元素的和
        int[] preSum = new int[arr.length + 1];
        for (int i = 1; i <= arr.length; i++) {
            preSum[i] = preSum[i - 1] + arr[i - 1];
        }
        // valueLower 使数组转化后最接近 target 且小于等于 target 的值
        int valueLower = -1;
        int low = 0, high = arr[arr.length - 1];
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int midSum = mutatedSum(arr, preSum, mid);
            int midPlus1Sum = mutatedSum(arr, preSum, mid + 1);
            if (midSum == target || midPlus1Sum == target) {
                return midSum == target ? mid : mid + 1;
            }
            if (midSum < target && midPlus1Sum > target) {
                valueLower = mid;
                break;
            }
            if (midSum < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        if (low > high) {
            // low 大于 high 表示数组无需改变任何值的和就最接近 target
            return high;
        }
        int valueLowerSum = mutatedSum(arr, preSum, valueLower); // 最接近 target 且小于 target 的和
        int valueUpperSum = mutatedSum(arr, preSum, valueLower + 1); // 最接近 target 且大于 target 的和
        return Math.abs(valueUpperSum - target) < Math.abs(valueLowerSum - target) ? valueLower + 1 : valueLower;
    }

    // 返回把升序数组 arr 中所有大于 x 的值都变为 x 后的元素和， preSum 是数组 arr 的前缀和
    private int mutatedSum(int[] arr, int[] preSum, int x) {
        int xIndex = binarySearch(arr, x);
        return preSum[xIndex] + x * (arr.length - xIndex);
    }

    // 在升序数组 arr 中查找 x 第一次出现的位置下标，若 x 不存在返回应该插入的位置。注意 arr 中可能有重复元素
    private int binarySearch(int[] arr, int x) {
        int res = -1;
        int low = 0, high = arr.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == x) {
                res = mid;
                break;
            } else if (arr[mid] > x) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        if (res == -1) {
            // 没找到 x
            return high + 1;
        } else {
            while (res > 0 && arr[res - 1] == arr[res]) {
                res--;
            }
            return res;
        }
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_1300_SumOfMutatedArrayClosestToTarget.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_1300_SumOfMutatedArrayClosestToTarget.java

---