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

发表于 更新于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        # 暴力枚举 + （二方法 + 前缀和）降低复杂度。 
        n = len(arr)
        arr.sort()
        pre = [0]  # 用一个前缀和 可以降低计算量。
        for i in arr:
            pre.append(pre[-1]+i) 
        # print(pre)
        diff = target
        ans = 0
        for i in range(0,max(arr)+1):
            idx = bisect.bisect_left(arr,i)
            tempsum = pre[idx] + (n-idx)*i
            if abs(tempsum-target) < diff:
                ans = i
                diff = abs(tempsum-target)
            # print(i,idx,tempsum,diff,ans)
        return ans