LeetCode_逆向思维_中等_453.最小操作次数使数组元素相等

x33g5p2x  于2022-08-17 转载在 其他  
字(0.9k)|赞(0)|评价(0)|浏览(203)

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

提示:
n == nums.length
1 <= nums.length <= 105
-109 <= nums[i] <= 109
答案保证符合 32-bit 整数

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/minimum-moves-to-equal-array-elements

2.思路

(1)逆向思维
① 如果直接求解发现有点困难,而仔细分析可知:本题最终的结果要求返回让数组所有元素相等的最小操作次数,而每次操作使 n - 1 个元素增加 1,在不考虑数组中具体元素值大小的前提下,该操作等价于使 1 个元素减少 1。所以本题可以等价于每次操作使 1 个元素减少 1,返回让数组所有元素相等的最小操作次数。

② 这样一来,题目就简单了许多,我们只需先求出数组 nums 中的最小值 minNum 以及所有元素之和 sum,由于每次操作使 1 个元素减少 1,那么最终使数组 nums 中所有元素相等的最小操作次数 res = sum - minNum * nums.length。

3.代码实现(Java)

//思路1————逆向思维
class Solution {
    public int minMoves(int[] nums) {
        int res = 0;
        int n = nums.length;
        // minNum 为数组 nums 中的最小值,初始值设为 nums[0]
        int minNum = nums[0];
        // sum 为数组 nums 中所有元素之和
        int sum = 0;
        for (int num : nums) {
            minNum = Math.min(minNum, num);
            sum += num;
        }
        return sum - minNum * n;
    }
}

相关文章

微信公众号

最新文章

更多