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

20200614

题目(难度:中等):

给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近  target （最接近表示两者之差的绝对值最小）。

如果有多种使得和最接近 target 的方案，请你返回这些整数中的最小值。

请注意，答案不一定是 arr 中的数字。

示例

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$104
• 1 <= arr[i], target <= $10^5$105

抛砖引玉

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

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

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/)

公号: 坑人的小书童