前言
又是好久没有更新了
正文
问题来源
本问题来自leetcode上的1300题。
问题描述
给你一个整数数组 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
分析：
首先求均值和将slice进行从小到大排序，求得均值之后将小于均值的总和进行记录，然后就会得到剩余的 target - ls_t 的值 然后我们可以求得剩余的平均值为多少，由 avg = (target-ls_t)/(l - i-1)更新。当前值大于剩余均值，则当前与后续的所有值都等于剩余均值（或者剩余均值加1）。
func findBestValue(arr []int, target int) int {
l := len(arr)
avg := target / l
sort.Ints(arr)
//abt_avg := int(math.Round(float64(target)/float64(l))) 可以替换成
abt_avg := avg
if target - avg*l > l/2 {
abt_avg ++
}
//arr自小到大，第一个都大于abt_avg（均值），直接就可以返回均值
if abt_avg <= arr[0] {
return abt_avg
}
//最后一个都小于均值，则返回arr最后一个值
if arr[l-1] <= abt_avg {
return arr[l-1]
}
// mean total less of average
// 小于平均值的数的总和
ls_t := 0
i := 0
for ; i < l; i++ {
// 当前值大于剩余均值，后面的值都会大于剩余均值
// 让当前以后的值都等于剩余均值或者剩余均值+1即可
if arr[i] > avg {
// 比较(l-i)*avg与(l-i)*(avg+1)两者谁更接近target-ls_t，因为题目要求两者相等时取更小的值
if int(math.Abs(float64(target-ls_t - (l-i)*avg))) <= int(math.Abs(float64(target-ls_t-(l-i)*(avg+1)))) {
return avg
}
return avg+1
} else if i != l - 1 { // 小于等于剩余均值，但是避免出现除0的情况
// 记录小于均值的总和
ls_t += arr[i]
// 更新剩余的均值
avg = (target-ls_t)/(l - i-1)
}
}
return arr[l-1]
}
做完之后看有没有好的解法，发现有人跟我的想法一样，少了一些判断
int cmp(const void* c1, const void* c2) {
return *(int*)c1 - *(int*)c2;
}
int findBestValue(int* arr, int arrSize, int target){
if (arr == NULL) {
return 0;
}
// 注意qsort的使用方法
qsort(arr, arrSize, sizeof(int), cmp);
int sum = 0;
for (int i = 0; i < arrSize; i++) {
int x = (target - sum) / (arrSize - i);
if (x < arr[i]) {
double t = ((double)(target - sum))/(arrSize - i);
if (t - x > 0.5) {
return x + 1;
} else {
return x;
}
}
sum += arr[i];
}
return arr[arrSize - 1];
}
要注意C语言中qsort的使用方法。
总结：
勤思考。
结语
不管怎么样好好加油。
