😃 1887.使数组元素相等的减少操作次数

给你一个整数数组 nums ，你的目标是令 nums 中的所有元素相等。完成一次减少操作需要遵照下面的几个步骤：

1. 找出 nums 中的 最大 值。记这个值为 largest 并取其下标 i （下标从 0 开始计数）。如果有多个元素都是最大值，则取最小的 i 。
2. 找出 nums 中的 下一个最大 值，这个值 严格小于 largest ，记为 nextLargest 。
3. 将 nums[i] 减少到 nextLargest 。

返回使 nums 中的所有元素相等的操作次数。

思路

基本思想

读完题目之后，发现数组的变化过程是一个分阶梯一步一步累加得到的，对于数组整体而言，是从最大值变为倒数第二的最大值，然后从倒数第二变成倒数第三，当所有的数都变成最小的数时就可以得到最终的答案，在这个变化过程中，有的数经历了几个阶梯的变化，但是这是有规律的

最大值变为最小值取决于数组中有多少类型的数字，如果有五种不同类型的数字，那么最大值变为最小值需要经历四次变化，对于倒数第二大的元素来说，需要经历三次变化，按照这种规律，我们只需要统计出每种元素的个数，然后将这些元素进行排序，此时就知道每种元素变为最小的元素需要经历几步，然后乘以当前元素的个数即可

核心就是对元素分类并排序，然后就可以知道每种元素需要多少次才能变化到最小值，将这些变化次数累加即可

执行流程

1. 使用哈希表统计每种元素的个数
2. 将所有的元素进行排序，从而知道每种元素变为最小值需要经历几步
3. 统计变化到最小值的变化次数结果

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    //统计有几种阶层，每个阶层有几个元素，直接用公式计算
    public int reductionOperations(int[] nums) {
        Map<Integer,Integer> map=new HashMap<>();
        //统计每种元素出现的次数
        for(int i=0;i<nums.length;++i){
            int count=map.getOrDefault(nums[i],0);
            map.put(nums[i],count+1);
        }
        //根据元素大小对级别进行排序
        Integer[] arr=map.keySet().toArray(new Integer[0]);
        Arrays.sort(arr);
        int res=0;
        for(int i=arr.length-1;i>0;--i){
            res+=map.get(arr[i])*i;
        }
        return res;
    }
}

总结

总的来说就是要总结解题过程中的规律，发现变化过程分阶梯，然后利用哈希表统计并计算每种元素变化到最小值需要几步，累加所有的变化步数即可