题目简介：
给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近 target （最接近表示两者之差的绝对值最小）。
如果有多种使得和最接近 target 的方案，请你返回这些整数中的最小值。
请注意，答案不一定是 arr 中的数字。
示例 1：
1
2
3
| 输入：arr = [4,9,3], target = 10
输出：3
解释：当选择 value 为 3 时，数组会变成 [3, 3, 3]，和为 9 ，这是最接近 target 的方案。
|
示例 2：
1
2
| 输入：arr = [2,3,5], target = 10
输出：5
|
示例 3：
1
2
| 输入：arr = [60864,25176,27249,21296,20204], target = 56803
输出：11361
|
提示：
1 <= arr.length <= 10^41 <= arr[i], target <= 10^5
思路：
由于target为正整数，所以value的下界为0，因为一旦value < 0，那么数组和必小于0，必和target差距越来越远。
而value的上界为数组中最大的值，因为一旦value >= max(arr)，数组的和就是本身的和，不会再发生改变了。
确定完上下界后，我们先可以将数组从小到大排序，并将每个元素的前缀和求出来，方便之后的操作。
接下来就对数组进行二分查找，找到arr[mid_index] > value的下标，即第一个比value大的值。
若value不大于数组中的所有值，那么此时mid_index == 0，数组和sum = arr.size() * value。
否则，sum = pre[mid_index - 1] + (arr.size() - mid_index) * value;即将下标之后的数都变成value再进行相加。
最后找到abs(sum - target)最小的值，返回此时的value即可。
tips:
- 难点在二分查找时的各种情况，需要注意的是找到第一个比
value大的值以及mid_index == 0时的判断方法(详情见代码)。
- 注意
while(left <= right)
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| class Solution {
public:
int findBestValue(vector<int>& arr, int target) {
vector<int> pre(arr.size(), 0);
sort(arr.begin(), arr.end());
pre[0] = arr[0];
for(int i = 1; i < arr.size(); i++){
pre[i] = pre[i - 1] + arr[i];
}
int min_abs = INT_MAX;
int min_value = 0;
for(int value = 0; value <= arr[arr.size() - 1]; value++){
int left = 0;
int right = arr.size() - 1;
int mid_index = 0;
while(left <= right){
mid_index = left + (right - left) / 2;
if(mid_index == 0){
if(arr[mid_index] > value)
break;
else
mid_index++;
}
if(arr[mid_index] > value && arr[mid_index - 1] <= value)
break;
else if(arr[mid_index] > value && arr[mid_index - 1] > value)
right = mid_index - 1;
else
left = mid_index + 1;
}
int sum;
if(mid_index == 0)
sum = arr.size() * value;
else
sum = pre[mid_index - 1] + (arr.size() - mid_index) * value;
if(abs(sum - target) < min_abs){
min_abs = abs(sum - target);
min_value = value;
}
}
return min_value;
}
};
|
