Leetcode 1300:转变数组后最接近目标值的数组和(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1300:转变数组后最接近目标值的数组和(超详细的解法!!!)

in leetcode with 0 comment

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

提示:

解题思路

首先查找问题不难想到二分法,二分法的判断函数也非常简单,就是计算满足条件的数组元素和sumtarget的关系。定义左右边界l=0r=max(arr),当sum<=target的时候,结果应该在[mid,r]区间内;否则,结果应该在[l,mid-1]区间内。

当我们查找到最后的位置时,此时sum<=target,我们还需要判断此时l+1对应的sum是不是离target更近。

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        def check(v):
            return sum(v if a > v else a for a in arr)

        l, r = 0, max(arr)
        while l < r:
            mid = (l + r + 1) // 2
            if check(mid) <= target:
                l = mid
            else:
                r = mid - 1

        if abs(target - check(l)) <= abs(check(l + 1) - target):
            return l
        return l + 1

还有一个不错的解法。我们可以现将数组从大到小排序,此时数组最右侧的元素就是最小值,如果以其作为最后的结果,那么此时的数组和应该是sum=len(arr)*arr[-1]。如果sum<=target,那么此时应该将sum扩大,怎么做呢?显然应该用arr[-2]作为结果去尝试,所以此时sum=(len(arr)-1)*arr[-2]+arr[-1]

为了操作的简单,我们可以每次将数组最右侧的元素弹出,然后通过target减去该元素,那么此时的sum=len(arr)*arr[-2](由于弹出一个元素,len(arr)减小了一位),判断此时sum<=target(由于此时target-=arr[-1])。

最后的结果显然就是target/len(arr),但是这个值是一个浮点数,如果小数部分>=0.5,那么我们应该上取整;否则,下取整。一个简单的操作方式就是int(target/len(arr)+0.49)

class Solution:
    def findBestValue(self, A: List[int], target: int) -> int:
        A.sort(reverse=True)
        maxA = A[0]
        while A and target >= A[-1] * len(A):
            target -= A.pop()
        return int(target/len(A) + 0.49) if A else maxA

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses