题目描述
给你一个整数数组 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 的方案。
|
算法
- 排序数组
- 遍历数组，找到 $i$ ，使得 $i$ 满足 $sum_{i-1} + arr[i] \times (arrSize - i) > target$ $(sum_i$表示从$0$至$i$的累加和$)$ 。
找到 $i$ 之后，表示结果 $value < arr[i]$，即从 $i$ 开始以后的元素都使用 $value$ 代替，于是 $value$ 约等于 $(target-sum_{i-1}) \div (arrSize - i)$，说约等于因为这里可能结果不是整数，所以需要根据题意找到最优解（最接近，最小）。
- 当 $i==arrSize$ 时，表示数组元素之和小于 $target$ ，返回数组的最大元素即可。
C代码
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
| #include <stdio.h>
#include <stdlib.h>
void bubble(int* arr, int arrSize);
int findBestValue(int* arr, int arrSize, int target);
int main()
{
int arr[] = {4,9,3};
int n = 3,target = 10;
int value = findBestValue(&arr[0],n,target);
printf("value=%d",value);
return 0;
}
void bubble(int* arr, int arrSize)
{
for(int i=0;i<arrSize-1;i++)
{
int flag = 1;
for(int j=arrSize-1;j>i;j--)
{
if(arr[j] < arr[j-1])
{
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
flag = 0;
}
}
if(flag == 1) break;
}
}
int findBestValue(int* arr, int arrSize, int target)
{
bubble(&arr[0],arrSize);
int i,sum=0;
for(i=0;i<arrSize;i++)
{
if(sum + arr[i]*(arrSize-i) > target) break;
sum += arr[i];
}
if(i == arrSize) return arr[arrSize-1];
int value = (target-sum)/(arrSize-i);
double value_1 = (double)(target-sum)/(arrSize-i);
if(value_1 - value > 0.5)
return value+1;
else
return value;
}
|
时间复杂度
算法的时间复杂度为排序算法时间复杂度 $O(n^2)$