【算法积累】最小操作次数使数组元素相等

ゝ一纸荒年。 2022-09-10 05:29 152阅读 0赞

# LeetCode 453 - 最小操作次数使数组元素相等（简单） #

[题目链接][Link 1]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ0NIwrLCuQ_size_20_color_FFFFFF_t_70_g_se_x_16]

# 数学推导及代码 #

假设原始数组之和为 s s s，最小操作次数为 a n s ans ans， a n s ans ans次操作后数组元素相等，为 t a r g e t target target。对于数组的 n − 1 n-1 n−1个元素都要进行增加1的操作，那么增加的总数是 a n s × ( n − 1 ) ans\\times (n-1) ans×(n−1)。则不难推断出 a n s × ( n − 1 ) + s = t a r g e t × n ans\\times (n-1)+s=target\\times n ans×(n−1)\+s=target×n只要确定了 t a r g e t target target的值，就能很简单地计算出 a n s ans ans。那么 t a r g e t target target的值该如何确定呢？经过分析可知，每次的操作都会对原数组的 n − 1 n-1 n−1个元素增加1，那么必定有对原数组的最小值 m i n min min增加1， a n s ans ans次操作后， 原先的最小值就变为了 m i n + a n s min+ans min\+ans，该值就是 t a r g e t target target。即有 t a r g e t = m i n + a n s target=min+ans target=min\+ans代入上式有 a n s × ( n − 1 ) + s = ( m i n + a n s ) × n ans\\times (n-1)+s=(min+ans)\\times n ans×(n−1)\+s=(min\+ans)×n整理得 a n s = s − m i n × n ans=s-min\\times n ans=s−min×n  
AC代码如下：  
语言：C++

class Solution { 
    public:
        int minMoves(vector<int>& nums) { 
            int s = 0;
            int min = * min_element(nums.begin(), nums.end());
            for (int i : nums) { 
                s += i;
            }
            int len = nums.size();
            return s - len * min;
        }
    };

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ0NIwrLCuQ_size_20_color_FFFFFF_t_70_g_se_x_16 1]

[Link 1]: https://leetcode-cn.com/problems/minimum-moves-to-equal-array-elements/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ0NIwrLCuQ_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/82b668d2207e4c2ea910f496e0e12ea9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQ0NIwrLCuQ_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/d29e68d591c748d6a174fb8977a9bfbc.png