Keshawn_lu's Blog

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

字数统计: 687阅读时长: 3 min
2020/06/14 Share

题目简介:

给你一个整数数组 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^4
  • 1 <= 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) //value不大于数组所有值
break;
else
mid_index++; //value大于arr[0]
}

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;
//value不大于数组所有值
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;

}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: