当前位置 博文首页 > AndyLiu1997的博客：leetcode1300. 转变数组后最接近目标值的数
给你一个整数数组 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^41 <= arr[i], target <= 10^5我们的整体思路是，通过枚举所有可能的value，通过二分来计算出每个value对应的转变数组和；然后找到最接近target的。
首先我们考虑value的取值范围，n = len(arr)，那么value的最小取值为target//n，如果小于这个值，得到的数组和肯定小于target；value的最大取值是max(arr)，因为将数组中大于value的变为value，如果大于max(arr)，相当于所有的数都没有改变。所以我们的枚举范围就是这个范围。
我们再考虑如何计算对应value的转变数组和，因为大于value的值转换为value，我们需要找到所有大于value的值，我们使用二分查找；现将arr排序，然后二分查找，在数组中找value；可能出现两种情况：
计算转变的数组和还需要另一个数据，那就是前面不需要改变的数的前缀和。如果我们二分查找找到的下标为idx，那么
[0,idx-1]的前缀和+(n-idx) * value，这个就是转变的数组和。我们在对arr排序之后就定义一个dp数组，dp[i]表示0到i-1的前缀和，dp[0] = 0。那么，当value = i时，转变的数组和为：
dp[idx]+i*(n-idx)
我们枚举所有的value，找到最接近target的即可。
class Solution:
def findBestValue(self, arr: List[int], target: int) -> int:
n = len(arr)
#首先将arr进行排序
arr.sort()
#arr中最大值，也是value可能的最大值
end = arr[-1]
#start为value可能的最小值
start = target // n
dp = [0 for _ in range(n)]
presum = 0
#dp[i]表示前i-1的和
for i in range(n):
dp[i] = presum
presum += arr[i]
#初始化ans
ans = 1000000
#二分查找，找到x在arr中的下标，如果没有x那么返回的就是最接近x，比x大的数的下标
def binary(x):
left = 0
right = n-1
while left < right:
mid = left + (right-left)//2
if arr[mid] >= x:
right = mid
else:
left = mid+1
return left
#开始遍历所有value可能的取值
for i in range(start,end+1):
idx = binary(i)
#算将大于arr[idx]的改为arr[idx],数组和与target的差，不断更新最小差ans，value记录对应的idx
if abs(target-dp[idx]-i*(n-idx)) < ans:
ans = abs(target-dp[idx]-i*(n-idx))
value = i
return value
上面的方法还可以进行优化。
我们简单粗暴的枚举了value的值，但是我们知道，随着value的增加，转变的数组和是严格递增的，也相当于排序的，所以我们可以使用二分查找，来找到最适合的value。我们找到使得转变数组和为target的值，如果找到了，那么就是答案。如果没找到，那么找到的是比target大，最接近target的数组和对应的value；还需要考虑小于target，最接近target的数组和对应的value，可以知道，即为找到的value-1。判断它们两个谁得到的离target最近，就是答案。
class Solution:
def findBestValue(self, arr: List[int], target: int) -> int:
n = len(arr)
#首先将arr进行排序
arr.sort()
#arr中最大值，也是value可能的最大值
end = arr[-1]
#start为value可能的最小值
start = target // n
dp = [0 for _ in range(n)]
presum = 0
#dp[i]表示前i-1的和
for i in range(n):
dp[i] = presum
presum += arr[i]
#初始化ans
ans = 1000000
#二分查找，找到x在arr中的下标，如果没有x那么返回的就是最接近x，比x大的数的下标,
#返回此时的转变数组和
def binary(x):
left = 0
right = n-1
while left < right:
mid = left + (right-left)//2
if arr[mid] >= x:
right = mid
else:
left = mid+1
return dp[left]+x*(n-left)
#对value取值进行二分查找
left = start
right = end
while left < right:
mid = left + (right-left)//2
if binary(mid) >= target:
right = mid
else:
left = mid + 1
#比较ans1和ans2谁更接近target，就是答案
ans1 = binary(left)
ans2 = binary(left-1)
if abs(target-ans2) <= abs(target-ans1):
return left-1
else:
return left
