使数组元素相等的减少操作次数 图解题解

这道题到底在问什么

输入

nums=[5,1,3]

输出

3

输入

nums=[1,1,1]

输出

0

输入

nums=[2,5,5,1,3]

输出

9

最优解：一步一步想明白

1. 3记牢一句:排序后从左往右,遇到严格更大的新值就让层级 cnt 加 1,每个元素把当前 cnt 累加进答案,总和就是操作次数。下面每帧都在套这句。
2. 4先看清画面。上面是原始数组 [2,5,5,1,3],顺序是乱的。右边这块计数面板记着两样东西,当前层级 cnt 和答案累计 ans,现在都是 0。要把这道题变简单,第一步是把数从小到大排好序,让相同的值挨在一起,方便一层一层地数。
3. 5把数组从小到大排成 [1,2,3,5,5]。为什么排序?因为最终所有数都要降到最小值 1,排好序之后,一个数「下面垫着几个更小的不同值」就一目了然。相等的两个 5 挨在了一起,它们属于同一层。排好序,接下来从左往右一位一位地数层级。
4. 6先看清整体结构。这里有 4 个不同的值,1、2、3、5,就是 4 个层级。最小的 1 是地面,任何数最终都要降到这里。一个数要操作几次,就看它下面垫着几层更小的不同值:2 降到 1 只跨 1 层;3 降到 1 要跨 2 层,走 3 到 2 再到 1;5 降到 1 要跨 3 层。下面从左往右,用一个计数器 cnt 把这些层级数出来。
5. 7把这一路的规则钉牢。层级计数 cnt 从 0 起步。从下标 1 开始,拿每个元素和它左边的邻居比:如果它严格更大,说明踩上了一个新台阶,cnt 加 1;如果和左邻相等,说明还在同一层,cnt 不变。不管是不是新层,当前这个元素都要把此刻的 cnt 累加进答案,因为 cnt 正好是它降到地面要走的层数。最左的第一个元素是最小值,它就是地面,不用降,贡献 0。
6. 8轮到最左边第 0 个元素,值是 1,它就是整个数组的最小值,也是所有数最终要降到的地面。它自己已经在最底层,不用做任何操作,贡献 0 次。cnt 保持 0,ans 保持 0。
7. 9把第 0 个标绿,当作地面记下。它是后面所有元素往下降的目标。答案面板还是 0。接着从下标 1 开始,一位一位往右数,看每一位比左邻是不是跨了新层。
8. 10接着看,轮到第 1 个元素,值是 2。左边蓝色那 1 个已经数过了。先把它和左边的邻居 1 拎出来比一比,下一帧判断它有没有踩上新层。此刻 cnt 还是 0。
9. 11把第 1 个的值 2 和左邻 1 比。2 严格大于 1,说明从左邻那一层往上又冒出了一个新层级,层级计数 cnt 从 0 加 1 变成 1。这个 cnt 的含义是:值 2 下面垫着 1 个更小的不同值,需要它一层层降过去。
10. 12把当前 cnt 累加进答案。值 2 要一层层降到最小值 1,路线是 2→1,正好 1 步,也就是 1 次操作。于是 ans 加上 1,从 0 变成 1,把这一位标绿。接着看下一个。
11. 13往右挪一位,轮到第 2 个元素,值是 3。左边蓝色那 2 个已经数过了。先把它和左边的邻居 2 拎出来比一比,下一帧判断它有没有踩上新层。此刻 cnt 还是 1。
12. 14把第 2 个的值 3 和左邻 2 比。3 严格大于 2,说明从左邻那一层往上又冒出了一个新层级,层级计数 cnt 从 1 加 1 变成 2。这个 cnt 的含义是:值 3 下面垫着 2 个更小的不同值,需要它一层层降过去。
13. 15把当前 cnt 累加进答案。值 3 要一层层降到最小值 1,路线是 3→2→1,正好 2 步,也就是 2 次操作。于是 ans 加上 2,从 1 变成 3,把这一位标绿。接着看下一个。
14. 16继续往右,轮到第 3 个元素,值是 5。左边蓝色那 3 个已经数过了。先把它和左边的邻居 3 拎出来比一比,下一帧判断它有没有踩上新层。此刻 cnt 还是 2。
15. 17把第 3 个的值 5 和左邻 3 比。5 严格大于 3,说明从左邻那一层往上又冒出了一个新层级,层级计数 cnt 从 2 加 1 变成 3。这个 cnt 的含义是:值 5 下面垫着 3 个更小的不同值,需要它一层层降过去。
16. 18把当前 cnt 累加进答案。值 5 要一层层降到最小值 1,路线是 5→3→2→1,正好 3 步,也就是 3 次操作。于是 ans 加上 3,从 3 变成 6,把这一位标绿。接着看下一个。
17. 19来到最后一位,轮到第 4 个元素,值是 5。左边蓝色那 4 个已经数过了。先把它和左边的邻居 5 拎出来比一比,下一帧判断它有没有踩上新层。此刻 cnt 还是 3。
18. 20把第 4 个的值 5 和左邻 5 比。两个相等,说明它俩是同一个值、属于同一层,没有踩上新台阶,所以 cnt 不增加,还是 3。这正是重复值的情形,前一个 5 和这个 5 站在同一层。
19. 21把当前 cnt 累加进答案。值 5 要一层层降到最小值 1,路线是 5→3→2→1,正好 3 步,也就是 3 次操作。于是 ans 加上 3,从 6 变成 9,把这一位标绿。所有元素都数完了,ans 就是最终答案。
20. 22把每个元素的贡献列出来看清楚。第 0 个 1 贡献 0;第 1 个 2 贡献 1;第 2 个 3 贡献 2;第 3 个 5 贡献 3;第 4 个 5 也贡献 3。加起来 0 加 1 加 2 加 3 加 3 等于 9。注意两个 5 各自都要降 3 层,所以各贡献 3,这就是为什么相同的值虽然同层、但每个都得单独操作。
21. 23回看整条路:排好序 [1,2,3,5,5],从左往右数层级,遇到严格更大的新值就让 cnt 加 1,每个元素把当前 cnt 累加进答案。cnt 一路是 0、1、2、3、3,累加得到 9。窍门就一句,排序后数层级,每个元素贡献「它下面更小的不同值个数」,总和就是操作次数。最终答案 9。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def reductionOperations(self, nums: List[int]) -> int:
        nums.sort()
        ans = cnt = 0
        for a, b in pairwise(nums):
            if a != b:
                cnt += 1
            ans += cnt
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int reductionOperations(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ans = 0, cnt = 0;
        for (int i = 1; i < nums.size(); ++i) {
            cnt += nums[i] != nums[i - 1];
            ans += cnt;
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int reductionOperations(int[] nums) {
        Arrays.sort(nums);
        int ans = 0, cnt = 0;
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] != nums[i - 1]) {
                ++cnt;
            }
            ans += cnt;
        }
        return ans;
    }
}

复杂度

面试官可能追问