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$
链接：https://leetcode-cn.com/problems/sum-of-mutated-array-closest-to-target
题解
1、排序 + 枚举 + 二分查找 + 前缀和
将数组从小到大排序，求得前缀和数组后，进行枚举每一个可能的值i，二分查找i在排序数组中的位置，根据该位置，计算处理后的数组和，求出一个最接近target的i。
class Solution {
public int findBestValue(int[] arr, int target) {
// 排序
Arrays.sort(arr);
int n = arr.length;
// 初始化前缀和数组
int[] prefix = new int[n + 1];
for (int i = 1;i <= n; ++i) {
prefix[i] = prefix[i-1] + arr[i-1];
}
// 二分查找
// 根据数组元素的值进行二分查找
int r = arr[n - 1];
int ans = 0, diff = target;
// 遍历每一个值[1,max]，取最优
for (int i = 1;i <= r;++i) {
int index = Arrays.binarySearch(arr,i);
if (index < 0) {
index = -index - 1;
}
int cur = prefix[index] + (n - index) * i;
if (Math.abs(cur - target) < diff) {
ans = i;
diff = Math.abs(cur - target);
}
}
return ans;
}
}
双重二分查找
二分查找一个value_lower，其处理后的数组和最接近target且不小于target；
二分查找一个value_upper，其处理后的数组和最接近target且大于target；
class Solution {
public int findBestValue(int[] arr, int target) {
// 排序
Arrays.sort(arr);
int n = arr.length;
// 求前缀合
int[] prefix = new int[n + 1];
for (int i = 1; i <= n; ++i) {
prefix[i] = prefix[i - 1] + arr[i - 1];
}
// 二分查找
int l = 0, r = arr[n - 1], ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
int index = Arrays.binarySearch(arr, mid);
if (index < 0) {
index = -index - 1;
}
int cur = prefix[index] + (n - index) * mid;
if (cur <= target) {
ans = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
int chooseSmall = check(arr, ans);
int chooseBig = check(arr, ans + 1);
return Math.abs(chooseSmall - target) <= Math.abs(chooseBig - target) ? ans : ans + 1;
}
public int check(int[] arr, int x) {
int ret = 0;
for (int num : arr) {
ret += Math.min(num, x);
}
return ret;
}
}
// 作者：LeetCode-Solution
// 链接：https://leetcode-cn.com/problems/sum-of-mutated-array-closest-to-target/solution/bian-shu-zu-hou-zui-jie-jin-mu-biao-zhi-de-shu-zu-/
从平均值开始，枚举，直到数组和大于目标值
该解法忽略了一个情况，就是数组的最大值小于平均值的情况，这时候，要返回最大值。
class Solution {
public int findBestValue(int[] arr, int target) {
int preSum = 0, sum = 0, flag = 0, cur = target/arr.length;//cur为枚举变量，从平均值开始可以降低一点时间复杂度
while(true){
preSum = sum;
sum = 0;
flag = 0;
for(int i = 0; i < arr.length; i++){
if(arr[i] > cur) sum += cur;
else{
sum += arr[i];
flag++;//记录跳入此分支的次数
}
}
if(flag == arr.length) return cur;//当数组中的数全比cur小，直接返回当前cur值就好（相当于数组中的最大值）
if(sum >= target) break;
cur++;
}
return Math.abs(target-preSum) > Math.abs(target-sum) ? cur : cur - 1;
}
}
// 作者：VincentHwong
// 链接：https://leetcode-cn.com/problems/sum-of-mutated-array-closest-to-target/solution/chun-bao-li-mei-xiang-dao-yong-er-fen-ye-bu-xu-yao/
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
