[LeetCode] 1887. Reduction Operations to Make the Array Elements Equal

Given an integer array nums, your goal is to make all elements in nums equal. To complete one operation, follow these steps:

1. Find the largest value in nums. Let its index be i (0-indexed) and its value be largest. If there are multiple elements with the largest value, pick the smallest i.
2. Find the next largest value in nums strictly smaller than largest. Let its value be nextLargest.
3. Reduce nums[i] to nextLargest.

Return the number of operations to make all elements in nums equal.

Example 1:

Input: nums = [5,1,3]
Output: 3
Explanation: It takes 3 operations to make all elements in nums equal:
1. largest = 5 at index 0. nextLargest = 3. Reduce nums[0] to 3. nums = [3,1,3].
2. largest = 3 at index 0. nextLargest = 1. Reduce nums[0] to 1. nums = [1,1,3].
3. largest = 3 at index 2. nextLargest = 1. Reduce nums[2] to 1. nums = [1,1,1].

Example 2:

Input: nums = [1,1,1]
Output: 0
Explanation: All elements in nums are already equal.

Example 3:

Input: nums = [1,1,2,2,3]
Output: 4
Explanation: It takes 4 operations to make all elements in nums equal:
1. largest = 3 at index 4. nextLargest = 2. Reduce nums[4] to 2. nums = [1,1,2,2,2].
2. largest = 2 at index 2. nextLargest = 1. Reduce nums[2] to 1. nums = [1,1,1,2,2].
3. largest = 2 at index 3. nextLargest = 1. Reduce nums[3] to 1. nums = [1,1,1,1,2].
4. largest = 2 at index 4. nextLargest = 1. Reduce nums[4] to 1. nums = [1,1,1,1,1].

Constraints:

• 1 <= nums.length <= 5 * 104
• 1 <= nums[i] <= 5 * 104

使数组元素相等的减少操作次数。

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

找出 nums 中的 最大 值。记这个值为 largest 并取其下标 i （下标从 0 开始计数）。如果有多个元素都是最大值，则取最小的 i 。
找出 nums 中的 下一个最大 值，这个值 严格小于 largest ，记为 nextLargest 。
将 nums[i] 减少到 nextLargest 。
返回使 nums 中的所有元素相等的操作次数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reduction-operations-to-make-the-array-elements-equal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题我提供两种做法，背后的思路差不多。

第一种做法是排序。对 input 数组排序之后，我们从右往左扫描，对于每一个 nums[i]，我们看一下他是否跟前一个数字 nums[i - 1] 一样，如果不一样，则说明需要操作。因为数组已经被排过序，所以操作次数 = len - i。操作次数的这个计算是因为当我们从右往左扫描的时候，一开始遇到的肯定是数组中的最大值；当我们遇到第一个小于数组中的最大值的数字时，我们需要改动的是数组最后那一段数字。

时间O(nlogn)

空间O(1)

Java实现

class Solution {
    public int reductionOperations(int[] nums) {
        int len = nums.length;
        int res = 0;
        Arrays.sort(nums);
        for (int i = len - 1; i >= 1; i--) {
            if (nums[i] != nums[i - 1]) {
                res += len - i;
            }
        }
        return res;
    }
}

第二种做法会利用到 priority queue 和 hashmap。我们先用 hashmap 统计每个不同数字的出现次数，然后把这个信息放入一个最大堆，堆顶是最大的数字。所以每次弹出一个元素的时候，我们把当前这个弹出的元素的出现次数再放入此时堆顶元素的出现次数，通过这种方式来记录操作次数。

时间O(nlogn)

空间O(n)

Java实现

class Solution {
    public int reductionOperations(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // 最大堆，堆顶是最大的数字
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (int key : map.keySet()) {
            int val = map.get(key);
            queue.offer(new int[] { key, val });
        }

        int res = 0;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            // 最大的数字及其出现次数
            int largestKey = cur[0];
            int largestVal = cur[1];
            if (!queue.isEmpty()) {
                // 次大的数字及其出现次数
                int[] second = queue.poll();
                int secondKey = second[0];
                int secondVal = second[1];
                res += largestVal;
                secondVal += largestVal;
                queue.offer(new int[] { secondKey, secondVal });
            }
        }
        return res;
    }
}

LeetCode 题目总结