1. 題目

給定一個長度為 n 的非空整數數組，找到讓數組所有元素相等的最小移動次數。每次移動可以使 n - 1 個元素增加 1。

示例: 輸入: [1,2,3]輸出: 3 解釋: 只需要3次移動（注意每次移動會增加兩個元素的值）：[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-moves-to-equal-array-elements
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 數學推導

• 設數組最小的數MinNum，數組和為sum，元素個數n，最終都是final
• 則最小的數肯定要變成final，每次都對最小的數+1是最少的次數（final-MinNum）
• 則 $sum+(final?MinNum)?(n?1)=final?n$
• $sum?MinNum?(n?1)=final$
• $answer=final?MinNum=sum?MinNum?n$
• 答案就是 $sum?MinNum?n$

class Solution { public:int minMoves(vector<int>& nums) {long MinNum = nums[0], sum = nums[0]; int i, n = nums.size();for(i = 1; i < n; ++i){if(nums[i] < MinNum)MinNum = nums[i];sum += nums[i];}//(final-MinNum)*(n-1)+sum == n*final//final = sum-(n-1)*MinNum//final-MinNum = sum-n*MinNumreturn sum-n*MinNum;} };

總結

以上是生活随笔為你收集整理的LeetCode 453. 最小移动次数使数组元素相等（数学）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。