【LeetCode453.最小操作次数使数组元素相等】

题目链接

453. 最小操作次数使数组元素相等 - 力扣（LeetCode）

实现思路

借鉴了一下大佬的思路（453. 最小操作次数使数组元素相等 - 力扣（LeetCode）），然后基于自己原本的暴力解法来理解题目。

• 最开始没看数据范围，直接模拟，每次对当前最小的n-1个数自增。
• 但是，这里可以发现一个思想，就是每次一定会对最初最小的那个数做自增操作。
• 现在，假设最终每个元素都变为t，操作次数为ans。那么(t*n - sum)/(n - 1) = ans.
• 由于每次都会对最初最小的那个数mn进行自增操作，因此mn + ans = t.

代码实现

class Solution {
public:int minMoves(vector<int>& nums) {// 1.一个直觉的想法，贪心，每次肯定是对最小的n-1个数进行加1，但是这么做时间复杂度很高// int n = nums.size();// int cnt = 0;// while (true) {//     int flag = 1;//     for (int i = 1; i < n; i++) {//         if (nums[i] != nums[i - 1]) {//             flag = 0;//             break;//         }//     }//     if (flag) return cnt;//     sort(nums.begin(), nums.end());//     for (int i = 0; i < n - 1; i++) {//         nums[i]++;//     }//     cnt++;// }// return -1;// 2.数学法// 假设最终每个元素是t,操作次数是ans// 那么 (t * n - sum) / (n - 1) = ans// 并且，由上面贪心的想法，也可以知道，数组中最小的元素，每次都要参与+1操作// 那么 min + ans = t// 联立 ans = sum - min * nint sum = 0;int n = nums.size();int mn = nums[0];for (int i = 0; i < n; i++) {sum += nums[i];mn = min(mn, nums[i]);}return sum - mn * n;}
};