跳转至

LeetCode: 1300. 转变数组后最接近目标值的数组和

1、题目描述

给你一个整数数组 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

2、解题思路

  • 首先判断和值是否小于等于target,如果是,直接返回最大值即可
  • 如何才能最接近目标值呢?
  • 假设数组中的元素都是一样的,最近接的就是
    • target//length
    • target//length +1
  • 考虑到小于value的数不能转化,找出所有小于target/length的值,令target减去,剩余的数字等分target的剩余部分,此时只需要考虑是否整除,不能整除考虑前后两个值的距离绝对值即可
import bisect
from itertools import accumulate


class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        total = sum(arr)
        if total <= target:
            return max(arr)
        arr_sort = sorted(arr)
        length = len(arr)
        acc = [0] + list(accumulate(arr_sort))
        pre = 0
        current = bisect.bisect_left(arr_sort, target / length)
        while pre != current:
            pre = current
            current = bisect.bisect_left(arr_sort, (target - acc[current]) / (length - current))

        res1 = (target - acc[current]) // (length - current)
        res2 = res1 + 1
        diff1 = abs(target - acc[current] - res1 * (length - current))
        res2_index = bisect.bisect_left(arr_sort, res2)
        diff2 = abs(target - acc[res2_index] - res2 * (length - res2_index))
        return res1 if diff1 <= diff2 else res2