一天一大 leet(转变数组后最接近目标值的数组和)难度:中等 DAY-14

20200614

题目(难度:中等):

示例

1. 示例 1

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

2. 示例 2

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

3. 示例 3

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

提示

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

抛砖引玉

1. 当arr中数据都替换成的最大值时都小于target是返回最大值
2. 循环arr的平均值到arr的最大值分别计算替换后数组的和

• 小于平均数的和+指针之前的数的和(大于平均数的地方)
• 计算和与target之前的差，每次比较上一次差与这次的大小，取最小值

/*** @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 = targetindex = arr.includes(aver) ? arr.indexOf(i) : 0;for (var i = 1; i <= len; i++) {arr[i - 1] < aver ? index = i : nullprefix[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;
};

1. 数组递增排序
2. 记录每个数字对应的和目标值差值的平均值

• 当这个数据大于平均值则说明符合条件的数字出现了
• 因为之后的数据在计算时需要更新为返回值，则此时返回值与当前这个数据越接近则最终求的和越接近
• 满足条件的最小整数，则四舍五入时舍弃0.5

/*** @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, targetfor i in range(1, r + 1):it = bisect.bisect_left(arr, i)cur = prefix[it] + (n - it) * iif 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;
}

1. 数组先排序，为了不断计算数组和的时候比较方便
2. 二分查找，找到使数组和最接近 target 的 value，二分查找的时候让左边界收缩，最终拿到的
   right 就是最接近的右边界，但是最终还要比较一下 right 和 right - 1 哪一个更接近
   如果 right - 1 和 right 计算的数组和与 target 的绝对值相等呢？那么返回 right - 1，
   题目要求是返回尽可能小的那个数

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;
}

1. 将数组arr按升序排序
2. 用remain存储与target值还差多少
3. 遍历arr过程中，计算tmp = remain / N - i，即达到目标值需要后面至少是N-i个tmp值，值得注意的是在js中/得到的是浮点数。
   1.当平均值tmp比当前值arr[i]小的时候，说明把当前下标i及后边的元素改成大于等于tmp的值时，最接近target。由于题目要求的是最小的value，所以tmp的小数点部位<=0.5时，都应该向下取整，反之向上取整。
   1.如果能够走完整个for循环，说明“target值很大”。所以原数组和就是距离target最近的值，所以直接返回arr[N - 1]，即原数组的最大值。
   注： 关于“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];
}

博客: 小书童博客(http://gaowenju.com/)

公号: 坑人的小书童