Leetcode-453题解

leetcode 453 题解
数学题。

数学题。

题目

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

提示：
n == nums.length
1 <= nums.length <= $10^5$
$-10^9$ <= nums[i] <= $10^9$
答案保证符合 32-bit 整数

思路

1. 首先想到，如果考虑所有数之间的差值，那么n-1个数加1，其实就是1个数减1。所以思路就变成了，在每次循环时，找到最大的数，对它减1，直到最小值和最大值之间的差距为0。这种想法当然是可行的，但是会超时。
2. 然后想到，每次应该对最大的数减去最小数与最大数之间的差值，即 $\text{nums}[\text{max_index}]-=|\text{max}(\text{nums})-\text{min}(\text{nums})|$。这样也会超时，因为每次减去差值之后，需要重新循环来寻找最大值。
3. 最后改进的思路就是，找出最小值，遍历数组中的每一个数，每个数与最小值之间的差值的和，即为要减去的值的总数。
   $$\text{count}=\sum_{i=0}^{n-1} \text{nums}[i]-\text{min}(\text{nums})$$

示例代码

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    int minMoves(vector<int>& nums) {
        int size=nums.size(), gmin=INT_MAX, count=0;
        auto min_it = min_element(nums.begin(), nums.end()); gmin=*min_it;
        for(int i=0;i<size;i++) {
            count+=nums[i]-gmin;
        }
        return count;
    }
};