题目(难度:中等):
给你一个整数数组 arr 和一个目标值 target ,请你返回一个整数 value ,使得将数组中所有大于 value 的值变成 value 后,数组的和最接近 target (最接近表示两者之差的绝对值最小)。
如果有多种使得和最接近 target 的方案,请你返回这些整数中的最小值。
请注意,答案不一定是 arr 中的数字。
输入:arr = [4,9,3], target = 10
输出:3
解释:当选择 value 为 3 时,数组会变成 [3, 3, 3],和为 9
这是最接近 target 的方案
输入:arr = [2,3,5], target = 10
输出:5
输入:arr = [60864,25176,27249,21296,20204], target = 56803
输出:11361
/**
* @param {number[]} arr
* @param {number} target
* @return {number}
*/
var findBestValue = function(arr, target) {
var r = arr[len - 1];
if (r*len <= target) return r;
arr.sort((a, b) => a - b);
var len = arr.length,
prefix = Array(len + 1).fill(0),
aver = Math.floor(target / len),
_result = 0,
diff = target
index = arr.includes(aver) ? arr.indexOf(i) : 0;
for (var i = 1; i <= len; i++) {
arr[i - 1] < aver ? index = i : null
prefix[i] = prefix[i - 1] + arr[i - 1];
}
for (var i = aver; i <= r; i++) {
if (arr.includes(i)) {
index = arr.indexOf(i) + 1;
}
var cur = prefix[index] + (len - index) * i;
if (Math.abs(cur - target) < diff) {
_result = i;
diff = Math.abs(cur - target);
}
}
return _result;
};
/**
* @param {number[]} arr
* @param {number} target
* @return {number}
*/
var findBestValue = function(arr, target) {
if (arr == null) {
return 0;
}
arr.sort((a, b) => a - b);
var arrSize = arr.length;
var sum = 0;
for (var i = 0; i < arrSize; i++) {
var x = (target - sum) / (arrSize - i);
if (x < arr[i]) {
return Math.round(x - 0.1);
}
sum += arr[i];
}
return Math.round(arr[arrSize - 1]);
}
class Solution:
def findBestValue(self, arr: List[int], target: int) -> int:
arr.sort()
n = len(arr)
prefix = [0]
for num in arr:
prefix.append(prefix[-1] + num)
r, ans, diff = max(arr), 0, target
for i in range(1, r + 1):
it = bisect.bisect_left(arr, i)
cur = prefix[it] + (n - it) * i
if abs(cur - target) < diff:
ans, diff = i, abs(cur - target)
return ans
一
先将数组arr排序,然后开始遍历。
使用变量sum_cur保存sum(sorted[0..i)]的值,用sum_pre 保存sum(sorted[0..i-1])的值,通过这两个变量循环往后计算求和。
首先,我们计算假如将所有数变成同一个数,这个value是多少, 这个初始的value不能大于arr中最小的数,因为如果如此, 就一定有数不能被它替代。
我们将这个数求和得到的结果存入approx中,作为以后对比的依据。
在此后的每次循环中,计算此时是否如果将所有sorted[i]及之后的数 全部替代,使得结果等于target。这个数同样不应该大于sorted[i], 不然sorted[i]就不能被替代。
此处要注意,假如在sorted[i-1]到sorted[i]之间存在新的value, 其小数等于0.5怎么办,如果出现了0.5那么说明剩余数的数量必然 是2的倍数,将其舍去或计入都会与target存在2的误差,为了使最后的 整数最小,应当舍去。方便起见,在Round前加一个小数解决。
假如这样求得的结果已经小于sorted[i-1]了,那么上一个数是结果。
/**
* @param {number[]} arr
* @param {number} target
* @return {number}
*/
var findBestValue = function (arr, target) {
let sorted = arr.sort((x,y)=>x-y);
let sums_cur = sorted[0];
let sums_pre = -1;
let value = Math.round(target / sorted.length);
value = Math.min(value, sorted[0]);
for (let i = 1; i < sorted.length; i ++){
sums_pre = sums_cur;
sums_cur = sums_pre + sorted[i];
let new_value = Math.round((target - sums_pre) / (sorted.length - i) - 0.000001);
new_value = Math.min(new_value, sorted[i]);
if (sorted[i-1] > new_value){
break;
}
value = new_value;
}
return value;
}
二
注: 关于“target值很大”的解释:首先按照题目的意思按照某个value值,用value替换掉大于value的值,这个做最后肯定是把整个数组和变小了。如果原数组的和小于target,那么按照某个value替换后更小于target了。
/**
* @param {number[]} arr
* @param {number} target
* @return {number}
*/
var findBestValue = function (arr, target) {
arr.sort((a, b) => a - b);
const N = arr.length;
let remain = target;
for (let i = 0; i < N; i++) {
let tmp = remain / (N - i);
if (tmp < arr[i]) {
return (tmp - Math.floor(tmp)) <= 0.5 ? Math.floor(tmp) : Math.ceil(tmp);
}
remain -= arr[i];
}
return arr[N - 1];
}
作者:坑人的小书童同志
链接:https://juejin.im/post/5ee5f2586fb9a047a226adf2
来源:掘金
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
三
var findBestValue = function(arr, target) {
let len = arr.length;
arr = arr.sort((a, b) => a - b);
let ans;
// 计算前缀和,优化计算数组和的时间
let prefixSum = [], tempSum = 0;
prefixSum[-1] = 0;
for (let i = 0; i < len; i++) {
tempSum += arr[i];
prefixSum[i] = tempSum;
}
// 二分查找范围是:0 ~ max(arr)
let left = 0, right = arr[len - 1], mid;
while (left < right) {
mid = left + ((right - left) >> 1);
let sum = calculateSum(arr, mid, len, prefixSum);
if (sum >= target) {
right = mid;
} else {
left = mid + 1;
}
}
// 比较 right 和 right - 1 两个数,哪一个使数组和最接近 target,返回它
// 这里比较 left 和 left - 1 也行,因为上面的二分结束时,left 和 right 是相等的
let rightSum = calculateSum(arr, right, len, prefixSum),
beforeRightSum = calculateSum(arr, right - 1, len, prefixSum);
let diffRight = Math.abs(rightSum - target),
diffBeforeRight = Math.abs(beforeRightSum - target);
return diffBeforeRight <= diffRight ? right - 1 : right;
};
// 使用前缀和,计算「使得将数组中所有大于 value 的值变成 value 后」的和
function calculateSum(arr, mid, len, prefixSum) {
let sum = 0, i = 0;
while (i < len) {
if (arr[i] > mid) break;
i++;
}
sum = (len - i) * mid + prefixSum[i-1];
return sum;
}