leetcode：1300. 转变数组后最接近目标值的数组和【二分】

分析

给定value我们可以得到当前的sum
可知，随着value的增加sum也是增加的
因此和target的距离应该是开口朝上的抛物线
这样的话，遍历所有可能的value值，找到第一个小于左右两边的即可

Ac code

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        n = len(arr)
        arr.sort()
        preSum = list(accumulate(arr))

        # logn
        def get_diff(value):
            idx = bisect_right(arr, value)
            # avoid 0 - 1 = -1
            if idx == 0:
                nowSum = n * value
            else:
                nowSum = preSum[idx - 1] + value * (n - idx)
            #print(preSum[idx - 1], value, n - idx)
            return abs(nowSum - target)
        
        
        minn, maxn = 0, arr[-1]
        for ans in range(minn, maxn + 1):
            #print(ans)
            #print(get_diff(ans - 1), get_diff(ans), get_diff(ans + 1))
            if get_diff(ans - 1) >= get_diff(ans) <= get_diff(ans + 1):
                return ans

总结

函数logn 外层on
和以前的外层on 函数logn
略有差距