文章目錄
- 題目
- 題目決議
- 解題代碼
- 暴力模擬(超時)
- 等效替代
題目
題目描述：
給你一個長度為 n 的整數陣列，每次操作將會使 n - 1 個元素增加 1 ，回傳讓陣列所有元素相等的最小操作次數，
示例1：
輸入：nums = [1,2,3]
輸出：3
解釋：
只需要3次操作（注意每次操作會增加兩個元素的值）：
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
示例2：
輸入：nums = [1,1,1]
輸出：0
題目決議
關于這題，最開始我也沒反應過來，還是看的官解才懂得原來是這種方法呀，最開始用的暴力模擬，然后超時了，，，
此題的解題思想：等效替代
- n-1 個數 +1 相對于 n 個數而言，于把值平鋪的效果而言，等效于一個數 -1，
- 所以題目可以看作是每次對一個數-1，減少多少次，能平鋪，很明顯直接 sum(max-min )即可，
解題代碼
暴力模擬(超時)
class Solution {
public:
void add(vector<int>& nums,int idx,int val){
for(int i=0;i<nums.size();i++){
if(i==idx){
continue;
}
nums[i]+=val;
}
}
int minMoves(vector<int>& nums) {
sort(nums.begin(),nums.end());
int res = 0;
while(1){
auto mn = min_element(nums.begin(),nums.end());
auto mx = max_element(nums.begin(),nums.end());
int gap = *mx-*mn;
if(gap==0){
break;
}
else{
add(nums,mx-nums.begin(),gap);
res += gap;
}
}
return res;
}
};
等效替代
class Solution {
public:
int minMoves(vector<int>& nums) {
int mn = *min_element(begin(nums),end(nums));
int res = 0;
for(auto&& t:nums) res += (t-mn);
return res;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/330136.html
標籤：其他
上一篇：開發有35歲危機，測驗怎么樣？