当前位置：首页 > news >正文

LeetCode 1300题：二分查找优化数组和接近目标值问题

news 2026/7/28 21:33:47

1. 问题背景与理解

leetcode 1300题"Sum of Mutated Array Closest to Target"是一个典型的算法优化问题。题目要求我们找到一个整数值value，使得将数组中所有大于value的元素替换为value后，数组的和最接近给定的目标值target。如果有多个value满足条件，则返回最小的那个。

这个问题在实际开发中有很多应用场景，比如资源分配、预算控制等。例如，我们需要将一组服务器的负载调整到一个目标值，但又不想过度调整，这时候就需要找到最接近目标值的调整方案。

2. 问题分析与解法思路

2.1 暴力解法分析

最直观的解法是暴力枚举所有可能的value值。由于数组中的元素都是正整数，value的可能取值范围是从0到数组中的最大值。对于每个value，我们计算转变后的数组和，然后找到最接近target的那个。

def findBestValue(arr, target): arr.sort() n = len(arr) min_diff = float('inf') best_value = 0 for value in range(0, arr[-1] + 1): total = 0 for num in arr: total += min(num, value) diff = abs(total - target) if diff < min_diff: min_diff = diff best_value = value elif diff == min_diff and value < best_value: best_value = value return best_value

这个解法的时间复杂度是O(n*max(arr))，当数组元素较大时效率很低。

2.2 优化思路：二分查找

观察到转变后的数组和sum(value)是关于value的单调非递减函数，我们可以使用二分查找来优化。具体思路是：

先对数组排序
确定value的可能范围[0, max(arr)]
在范围内进行二分查找，计算每个中间值对应的数组和
根据数组和与target的关系调整查找范围

def findBestValue(arr, target): arr.sort() n = len(arr) prefix = [0] for num in arr: prefix.append(prefix[-1] + num) left, right = 0, arr[-1] best_value = 0 min_diff = float('inf') while left <= right: mid = (left + right) // 2 # 找到第一个大于mid的元素索引 index = bisect.bisect_left(arr, mid) total = prefix[index] + (n - index) * mid diff = abs(total - target) if diff < min_diff or (diff == min_diff and mid < best_value): min_diff = diff best_value = mid if total < target: left = mid + 1 else: right = mid - 1 return best_value

这个解法的时间复杂度是O(nlogn)，主要来自排序和二分查找。

3. 关键实现细节

3.1 前缀和优化

为了快速计算转变后的数组和，我们可以预先计算前缀和。这样对于任意value，我们可以：

使用二分查找找到第一个大于value的元素位置index
前index个元素的和就是prefix[index]
后面n-index个元素都被替换为value，和为(n-index)*value
总数组和就是prefix[index] + (n-index)*value

3.2 边界条件处理

需要特别注意以下边界条件：

当value=0时，所有元素都被替换为0
当value≥max(arr)时，数组和就是原数组和
当target≤0时，最佳value显然是0
当target≥sum(arr)时，最佳value是max(arr)

3.3 查找终止条件

二分查找的终止条件是left>right。在查找过程中，我们需要记录当前的最小差值min_diff和对应的best_value。当遇到相同差值时，选择较小的value。

4. 复杂度分析

时间复杂度：O(nlogn)
- 排序：O(nlogn)
- 前缀和计算：O(n)
- 二分查找：O(logn)，每次查找需要O(logn)时间计算数组和
空间复杂度：O(n)，用于存储前缀和

5. 实际应用与变种

5.1 资源分配问题

这个问题可以应用于资源分配场景。例如，有n个项目需要资金，每个项目原始申请资金为arr[i]，但总预算只有target。我们需要确定一个上限value，使得：

任何项目的资金不超过value
总资金最接近target
如果有多个value满足条件，选择最小的那个

5.2 变种问题

如果允许部分元素不被替换（即可以选择性地替换某些元素），问题会变得更复杂，可能需要动态规划解决
如果数组元素可以是负数，需要调整算法逻辑
如果要求数组和必须不小于target，可以修改二分查找的条件

6. 常见错误与调试技巧

6.1 常见错误

忘记处理多个value产生相同差值的情况
二分查找范围设置不正确（应该从0到max(arr)）
前缀和计算错误（注意前缀和数组的长度是n+1）
没有考虑target小于0或大于sum(arr)的边界情况

6.2 调试技巧

对于小规模输入，先手动计算预期结果
打印二分查找过程中的中间值和对应的数组和
检查前缀和计算是否正确
特别注意边界条件的测试用例

7. 代码优化与最佳实践

7.1 进一步优化

我们可以进一步优化二分查找的实现：

提前计算sum(arr)，用于处理target≥sum(arr)的情况
在二分查找前先检查边界条件
使用内置的bisect模块提高查找效率

7.2 Python实现优化版

import bisect def findBestValue(arr, target): arr.sort() n = len(arr) prefix = [0] for num in arr: prefix.append(prefix[-1] + num) total_sum = prefix[-1] if target >= total_sum: return arr[-1] left, right = 0, arr[-1] best_value = 0 min_diff = float('inf') while left <= right: mid = (left + right) // 2 index = bisect.bisect_left(arr, mid) current_sum = prefix[index] + (n - index) * mid diff = abs(current_sum - target) if diff < min_diff or (diff == min_diff and mid < best_value): min_diff = diff best_value = mid if current_sum < target: left = mid + 1 else: right = mid - 1 return best_value

7.3 测试用例设计

好的测试用例应该包括：

常规情况
target小于最小可能和
target大于最大可能和
多个value产生相同差值
数组包含重复元素
数组只有一个元素

示例测试用例：

assert findBestValue([4,9,3], 10) == 3 assert findBestValue([2,3,5], 10) == 5 assert findBestValue([60864,25176,27249,21296,20204], 56803) == 11361 assert findBestValue([1,2,3], 0) == 0 assert findBestValue([1,2,3], 100) == 3 assert findBestValue([5], 10) == 5