What is the main strategy for Sum of Mutated Array Closest to Target?

Use binary search over the possible integer values and compute the mutated sum at each step to minimize the absolute difference to target.

Should the answer always be an element from the original array?

No, the optimal mutation value may not exist in the original array; the solution searches the full valid integer range.

How do tie situations get resolved?

If multiple values yield the same minimal difference, return the smallest integer according to problem instructions.

Why use prefix sums in this problem?

Prefix sums allow efficient calculation of the mutated array sum at each candidate value during binary search, reducing time complexity.

What is the failure mode if you don’t sort first?

Without sorting, prefix sums may be incorrect, leading to wrong sum computations and failing test cases for large arrays.

#1300

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

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

给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近 target （最接近表示两者之差的绝对值最小）。如果有多种使得和最接近 target 的方案，请你返回这些整数中的最小值。请注意，…

数组二分查找排序

题目描述

给你一个整数数组 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^4
1 <= arr[i], target <= 10^5

lightbulb

解题思路

方法一：排序 + 前缀和 + 二分查找 + 枚举

我们注意到，题目中要把所有大于 value 的值变成 value，并且求和，因此我们可以考虑先对数组 arr 进行排序，然后求出前缀和数组 $s$ ，其中 $s[i]$ 表示数组前 $i$ 个元素之和。

接下来，我们可以从小到大枚举所有 value 值，对于每个 value，我们可以通过二分查找找到数组中第一个大于 value 的元素的下标 $i$ ，此时数组中大于 value 的元素个数为 $n - i$ ，因此数组中小于等于 value 的元素个数为 $i$ ，此时数组中小于等于 value 的元素之和为 $s[i]$ ，数组中大于 value 的元素之和为 $(n - i) \times \textit{value}$ ，因此数组中所有元素之和为 $s[i] + (n - i) \times \textit{value}$ 。如果 $s[i] + (n - i) \times \textit{value}$ 与 target 的差的绝对值小于当前的最小差值 diff，则更新 diff 和 ans。

枚举完所有 value 后，即可得到最终答案 ans。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 arr 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        arr.sort()
        s = list(accumulate(arr, initial=0))
        ans, diff = 0, inf
        for value in range(max(arr) + 1):
            i = bisect_right(arr, value)
            d = abs(s[i] + (len(arr) - i) * value - target)
            if diff > d:
                diff = d
                ans = value
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n log m) where n is array length and m is the max element, because each binary search step evaluates the sum in O(n) using prefix sums. Space complexity is O(n) for the sorted array and prefix sums.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Sorting the array before search may improve efficiency and is worth mentioning.
question_mark
Binary search over the answer space is the expected approach; brute force will likely exceed time limits.
question_mark
Tracking minimal absolute difference and tie-breaking is critical; omitting it may indicate incomplete understanding.

warning

常见陷阱

外企场景

error
Failing to sort the array first, which can cause incorrect prefix sums.
error
Not handling tie cases properly when multiple values yield the same minimal difference.
error
Iterating every possible value instead of using binary search, leading to time limit exceeded.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Maximize the sum without exceeding target instead of minimizing difference.
arrow_right_alt
Return all possible integers yielding the minimal difference.
arrow_right_alt
Allow negative numbers in the array, testing binary search correctness with extended ranges.

help

常见问题

外企场景

继续练习