力扣_1300. 轉變數組後最接近目標值的數組和
- 2020 年 6 月 14 日
- 筆記
- C++, 轉變數組後最接近目標值的數組和
題目描述：
給你一個整數數組 arr 和一個目標值 target ，請你返回一個整數 value ，使得將數組中所有大於 value 的值變成 value 後，數組的和最接近 target （最接近表示兩者之差的絕對值最小）。
如果有多種使得和最接近 target 的方案，請你返回這些整數中的最小值。
請注意，答案不一定是 arr 中的數字。
提示中給的是二分法，而二分法官方解答已經很詳細了，下面是我的解體思路
首先，這道題的根本目的是在數組中切一刀。那麼具體在哪切一刀呢？
根據題意我們可以確定value的最小值是1，最大值可以取到arr數組的最大值。那麼最暴力的方法當然是直接再value的取值範圍里採用循環遍歷，找出value的值。當然，這樣做的時間成本太大了，力扣是不會給你分的（我已經試過了）。
為了清晰的描述我的思路，這裡先舉個栗子。
為了方便，我這裡直接給出一個已經排列好的數組。（數組的排列可以直接使用sort()函數）
arr[]={7,9,12,17,19,25} target=80
這裡的數組大小是6，要讓它的和接近80，那麼也就是說這6個數的平均值要接近13.33（80/6),也就是說，此數組不可能在12的前面切一刀
若在12後面17前面切一刀，新數組arr[7,9,12,x,x,x]，為了使數組和更接近target：
那麼 80-7-9-12=52 x=52/3=17.33<17.5，
所以X最合適的值就是17，即value=17
程式碼如下：
class Solution {
public:
int findBestValue(vector<int>& arr, int target) {
sort(arr.begin(),arr.end()); //將數組從小到大排列
int pre=0,rest=arr.size(); //將數組切成兩段 pre表示前一段數字的和，rest表述後一段數字的個數
double temp; //存儲平均數x的值
for(int i=0;i<arr.size();i++){
temp = double(target-pre)/rest; //循環遍歷
if(temp<=arr[i]){
if(temp-int(temp)>0.5) return int(temp)+1; //若是平均值小於數組內的最小值，那麼value就等於四捨五入後的平均值
return int(temp);
}
pre+=arr[i];
rest–;
}
return arr[arr.size()-1]; //若是平均值大於數組內的最大值，那麼value就等於數組內的最大值
}
};
如果有什麼問題，歡迎大家指正！
