Created time
May 25, 2022 02:35 PM
date
status
category
Origin
summary
tags
type
URL
icon
password
slug
最小操作次数使数组元素相等
给你一个长度为
n 的整数数组，每次操作将会使 n - 1 个元素增加 1 。返回让数组所有元素相等的最小操作次数。答案保证符合 32-bit 整数。相关标签：数组, 数学。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. The answer is guaranteed to fit in a 32-bit integer. Related Topics: Array, Math.这题是给我们一个非空数组，然后我们每一次可以进行的操作是任选n-1个元素，然后把这n-1个元素全部加一。然后问我们最少进行多少次操作，可以将数组里面所有的数变成相同的数。
那么我们可以发现你任选n-1个元素加一其实可以看成等价于任选一个元素减一，因为我们最后是要把所有元素变成相同的值。我们其实关心的是它的相对的一个值，而不是它的一个绝对值，所以我们任选n-1个元素全部加一等价于选择剩下的那个元素让它减一。
那么这个问题就变成了就是说每次我们选择一个元素，然后让这个元素减一，然后将所有元素变成相同值的话，最少需要进行多少次操作。
那么这样的话这个题就很简单了，我们先找一下所有数里面的最小值，由于这里面只有减法操作，所有数只能往下减。所以我们找到这个最小值之后，我们其它所有数至少要减到最小数这个水平。因为最小值是没法增加到，所以我们所有数至少减到最小数这个水平。那么由于我们要求的是最小操作次数，那么我们将其它所有值都减到最小数的水平就可以了，那么最后的操作方案数就是每个数和最小值的差的和。求最小值和求和的时间复杂度都是 ，这个做法是的。
也可以直接使用C++ STL中的 accumulate 和 min_element。