資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告