数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++中求最接近目标值的变异数组之和
假设我们有一个整数数组arr和一个目标值target，我们需要找到一个整数，使得当我们将数组中所有大于该值的整数都更改为该值时，数组的和尽可能接近目标值。如果两者相同，则返回最小这样的整数。例如，如果数组为[4,9,3]，目标值为10，则输出为3，因为使用3，数组将变为[3,3,3]，总和为9，这是最接近10的值。
为了解决这个问题，我们将遵循以下步骤：
- n := 数组大小，avg := 总和 / n，设置sum := 0，cnt := 0
- 对于范围0到n – 1中的i
- 如果arr[i] <= avg，则sum := sum + arr[i]，并将cnt增加1
- 如果target – sum = 0，则返回avg
- high := (target - sum) / (n - cnt) 的上取整
- low := (target - sum) / (n - cnt) 的下取整
- lowDiff := |target – (low*(n - cnt) + sum)|
- highDiff := |target – (high*(n - cnt) + sum)|
- 如果lowDiff <= highDiff，则返回low
- 返回high。
让我们来看下面的实现来更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findBestValue(vector<int>& arr, int target) {
int n = arr.size();
int avg = target / n;
int sum = 0;
int cnt = 0;
for(int i = 0; i < n; i++){
if(arr[i] <= avg){
sum += arr[i];
cnt++;
}
}
if(target - sum == 0)return avg;
int high = ceil(((target - sum) * 1.0)/ ((n - cnt) * 1.0));
int low = floor(((target - sum) * 1.0) / ((n - cnt) * 1.0));
int lowDiff = abs(target - (low * (n - cnt) + sum));
int highDiff = abs(target - (high * (n - cnt) + sum));
if( lowDiff <= highDiff)return low;
return high;
}
};
main(){
vector<int> v = {4,9,3,2};
Solution ob;
cout << (ob.findBestValue(v, 10));
}输入
[4,9,3,2] 10
输出
3
更新于：2020年5月2日
278 次浏览
广告