新知一下
海量新知
6 0 8 2 1 8 8

​LeetCode刷题实战453:最小操作次数使数组元素相等

程序IT圈 | 程序员编程技术 2021/11/30 09:20

今天和大家聊的问题叫做 最小操作次数使数组元素相等 ,我们先来看题面:

https://leetcode-cn.com/problems/minimum-moves-to-equal-array-elements/

Given an integer array nums of size n, return the minimum number of moves required to make all array elements equal.

In one move, you can increment n - 1 elements of the array by 1.

给你一个长度为 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

解题

https://blog.csdn.net/qq_45260619/article/details/113715613

我们需要先对数组进行排序,这样可以找到数组中最大值和最小值m a x 和 m i n max和minmax和min,令 d i f = m a x − m i n dif = max - mindif=max−min,意思是:我们对除了最大值以外的数全部加上dif,这样又可以产生新的最大值和最小值,我们只需要重复进行操作即可。

那么我们怎样迅速找到最大值和最小值呢?

我们进行操作之前的数组是:[ a 1 , a 2 , a 3... , a n ] [a1,a2 ,a3...,an][a1,a2,a3...,an],此时是有序的,那么我们对除了 a n anan 的所有数加上 d i f difdif 之后,那么 a 1 > = a n , a 2 > = a n ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ a ( n − 1 ) > = a n a1 >= an , a2 >= an ······ a(n-1) >= ana1>=an,a2>=an⋅⋅⋅⋅⋅⋅a(n−1)>=an,那么此时数组中的最大值变为了 a ( n − 1 ) a(n-1)a(n−1) , 最小值仍然是 a 0 a0a0 , 那么再次循环,最大值变为了 a ( n − 2 ) a(n-2)a(n−2) ,最小值仍然是 a 0 a0a0 ,如此循环即可找到答案。

class Solution {

public:

    int minMoves(vector<int>& nums) {

        sort(nums.begin() , nums.end());

        int res = 0;

        for(int i = nums.size() - 1; i > 0; i--)

        {

            res += nums[i] - nums[0];

        }

        return res;

    }

};


更多“算法”相关内容

更多“算法”相关内容

新知精选

更多新知精选