LeetCode 1887. 使数组元素相等的减少操作次数 题解，理解操作次数的含义。

题目

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

https://leetcode.cn/problems/reduction-operations-to-make-the-array-elements-equal/

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

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

TreeMap模拟

思路

我首先想到了模拟，每一轮我们需要拿出当前集合中最大元素，以及值小于最大值的元素。

为了方便拿出数据，我们可以使用树结构，或者跳表结构，这里我用了基于红黑树的TreeSet。

为了支持等值元素，内部存储int[]格式，arr[0]表示元素值 arr[1]表示元素下标。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

static class TreeMapSolution {

    /**
     * 空间复杂度 O(n)
     * 时间复杂度：
     * - 初始化treeMap n*logn，之后进行n轮比较，每次取出数据需要logn
     * - 最优情况下元素初始就等值，比较复杂度 一次logn
     * - 最差情况下每个数据都不等，比较趋近 n^2 次，复杂度 n^2*logn
     * - 综合时间复杂度 n^2*logn
     */
    public int reductionOperations(int[] nums) {
        // int[] arr[0]表示元素值 arr[1]表示元素下标
        // 按元素值增序排序，元素等值按下标排序
        NavigableSet<int[]> set = new TreeSet<>((a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            }
            return a[1] - b[1];
        });
        // nlogn初始化
        for (int i = 0; i < nums.length; i++) {
            set.add(new int[]{nums[i], i});
        }
        int ans = 0;
        while (true) {
            // O(logn)取出最大值
            int[] biggest = set.pollLast();
            // 方便lower直接拿出值比当前元素更小的
            // 同时暂存原最大值、最大值下标
            int tmpBiggestVal = biggest[0];
            int tmpBiggestIdx = biggest[1];
            biggest[0] = biggest[0] - 1;
            biggest[1] = Integer.MAX_VALUE;
            int[] lower = set.lower(biggest);
            if (lower == null || tmpBiggestVal == lower[0]) {
                return ans;
            }
            biggest[0] = lower[0];
            biggest[1] = tmpBiggestIdx;
            set.add(biggest);
            ans++;
        }
    }
}

复杂度分析

时间
  • 初始化treeMap 复杂度n*logn，之后进行n轮比较，每次取出数据需要logn；
  • 最优情况下元素初始就等值，比较复杂度 一次logn；
  • 最差情况下每个数据都不等，比较趋近 n^2 次，复杂度 n^2*logn；
  • 综合时间复杂度 n^2*logn；

时间复杂度最差n^2*logn，这也是部分用例超时的原因。

空间

额外维护了一个树结构，空间复杂度O(n)。

排序计数

思路

解法1时间效率不满足要求！

分析最差情况用例，可以看出每个元素我们都经过接近n轮的比较。

实际上等值元素删减为比其更小的最大元素 对应操作次数是一致的。

我们可以使用排序+计数的方式解决问题。

算法过程：

  1. 对入参数组排序；
  2. 从第二个元素开始判断，如果当前元素与前置元素不等，说明步长currOperationCnt需要+1；
  3. 累加步长；

此算法核心：意识到题目只需要求删减的步数，因此我们维护、统计步数即可。

而步数只有在排序集合当前元素与前置元素不等时才需要更新。

代码

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

static class Sort {
    /**
     * 时间复杂度：排序使用 O(n*logn)
     * 空间复杂度：快排使用递归栈消耗 O(logn)
     */
    public int reductionOperations(int[] nums) {
        Arrays.sort(nums);
        int ans = 0;
        // 距离nums[0]的操作次数
        // 比如 1 3 5 ，最终题干要求都变成1，那么3变成1需要一次操作，5变成1，则需要先变成3再变成1，也就是 op[5-1]=op[5-3]+op[3-1];
        int currOperationCnt = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                currOperationCnt++;
            }
            ans += currOperationCnt;
        }
        return ans;
    }
}

复杂度分析

时间

排序使用 O(n*logn) 时间。

空间

快排使用递归栈消耗 O(logn)。

计数排序

思路

意识到题目只需要求删减的步数，因此我们维护、统计步数即可。

在解法2的基础上，我们可以考虑计数排序。

代码

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

static class CountingSort {

    /**
     * 时间复杂度：O(5 * 10000)
     * 空间复杂度：O(5 * 10000)
     */
    public int reductionOperations(int[] nums) {
        int maxN = 5 * 10000;
        int[] countArr = new int[maxN + 1];
        for (int num : nums) {
            countArr[num]++;
        }
        int ans = 0;
        int step = -1;
        for (int i = 1; i < countArr.length; i++) {
            if (countArr[i] > 0) {
                step++;
                ans += countArr[i] * step;
            }
        }
        return ans;
    }
}

复杂度分析

时间

遍历我们的计数数组，使用 O(5 * 10000) 时间。

空间

计数数组开辟了O(5 * 10000)大的空间。