欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-07 23:02:26
...

20200614

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

题目(难度:中等):

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

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

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

示例

  1. 示例 1
输入:arr = [4,9,3], target = 10
输出:3
解释:当选择 value 为 3 时,数组会变成 [3, 3, 3],和为 9 ,这是最接近 target 的方案。
  1. 示例 2
输入:arr = [2,3,5], target = 10
输出:5
  1. 示例 3
输入:arr = [60864,25176,27249,21296,20204], target = 56803
输出:11361

提示

  • 1 <= arr.length <= 10410^4
  • 1 <= arr[i], target <= 10510^5

抛砖引玉

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

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

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

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

公号: 坑人的小书童
一天一大 leet(转变数组后最接近目标值的数组和)难度:中等 DAY-14