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

冷不防 2023-10-06 23:33 18阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 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;
        }
    }