难度: Medium
给你一个整数数组 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运行时间: 34 ms
内存: 17.0 MB
class Solution:
def findBestValue(self, arr: List[int], target: int) -> int:
summ = sum (arr)
if summ <= target :
return max(arr)
l = len (arr)
val = target // l
summ , last =0, 0
while summ < target :
last = summ
summ = 0
for i in range(l):
summ += arr[i] if val > arr[i] else val
val += 1
return val-2 if abs(target-summ) >= abs(target-last) else val -1
这个题解采用了贪心算法的思路。首先计算数组的和，如果和小于等于目标值，则直接返回数组中的最大值。如果和大于目标值，那么就需要找到一个值value，使得将数组中所有大于value的值变成value后，数组的和最接近目标值。初始时，value设为target除以数组长度，然后逐渐增加value，每次增加后重新计算数组的和，直到和大于等于目标值为止。最后，比较value和value-1哪个使得数组和更接近目标值，返回较优的那个。
时间复杂度: O(n^2)
空间复杂度: O(1)
class Solution:
def findBestValue(self, arr: List[int], target: int) -> int:
summ = sum(arr) # 计算数组的和
if summ <= target :
return max(arr) # 如果和小于等于目标值，直接返回数组最大值
l = len(arr)
val = target // l # 初始value值
summ, last = 0, 0
while summ < target :
last = summ # 记录上一次的和
summ = 0
for i in range(l):
summ += arr[i] if val > arr[i] else val # 更新数组的和
val += 1 # 增加value值
return val-2 if abs(target-summ) >= abs(target-last) else val -1 # 返回较优的value值
选择初始的 value 为 target 除以数组长度是基于将目标值平均分配到每个数组元素的直观想法。如果我们希望调整数组的元素，使得它们的总和尽可能接近目标值 target，那么一个理想的起点是将 target 均等地分配给每个元素，这样每个元素的目标值就是 target 除以数组长度。这不仅提供了一个合理的起始估计值，而且简化了算法的实现，因为这通常会是调整过程中的一个中间值。
题解中的方法通过逐步增加 value 并重新计算整个数组的和不是最高效的方法，因为每次 value 改变都需要遍历整个数组来计算新的总和。一种可能的改进方法是使用排序和前缀和。首先，对数组进行排序。然后，利用前缀和技术来快速计算在不同的 value 设置下数组的和。使用二分查找方法来确定最接近目标的 value，这样可以显著减少必要的迭代次数和总的计算量。
确实存在逻辑上的疏漏。在算法中，应当比较的是在最后一次迭代中使得和刚好大于等于目标值的 value 和前一次迭代的 value-1。因此，应当比较 value-1 和 value-2 的总和与目标值的接近程度，而非直接返回 value-2 或 value-1。需要修正逻辑，以确保比较和选择是正确的。
题解中未明确说明这一点，但理想的实现应该是这样的：在确定了可能的 value 后（即值使得总和最接近目标值的两个候选值），应当选择这两者中较小的一个，如果它们导致的总和相同的话。确保返回最小的 value 可以通过在迭代过程中持续跟踪并更新当找到一个新的、更接近目标值的 value 时，只有在这个新的 value 小于或等于之前记录的相同效果的 value 时，才更新记录。