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

每次把最大值削到次大值，最后要削几次

给一个整数数组 nums，一次操作是这样：挑出当前的最大值，把它减到数组里严格比它小的那个次大值。一直操作，直到所有数都相等，返回一共操作了多少次。题面给的 nums=[2,5,5,1,3]，最后需要 9 次；而 [1,1,1] 本来就全相等，答案是 0。

照题面每次找最大值去削，数据一大就卡死

题面把操作描述得很具体，容易让人照着做：扫一遍找到最大值，减到次大值，再扫再减。可每削一次只降一个数、还要重新找一遍最大值，一次遍历 O(n)，削的次数最坏能到 O(n²) 量级，nums 一长就超时。这种模拟把「先削谁后削谁」当成了变量，而它其实根本不影响结果。

一个数削几次，只看它脚下垫着几个更小的不同值

想跳出模拟，先弄清一个数的操作次数到底由什么决定。每次操作只把一个数往下挪一层——降到严格小于它的次大值，而所有数最终都要落到最小值。那么某个数要削几次，就等于它和最小值之间隔着多少个不同的值，跟先削谁毫无关系。既然如此，把数组从小到大排好，一个数下面垫着几个更小的不同值就摆在眼前，从左往右数一遍，每个数的次数就都加出来了。

遇到更大的新值才加层，相等的算同一层

落到代码，维护一个层数 cnt 从 0 起，从第二个元素开始，拿每个数和它左邻比：严格更大，说明踩上了新一层，cnt 加 1；相等，还在同一层，cnt 不动。不管是不是新层，当前这个数都要把此刻的 cnt 累加进答案，因为它自己要一层层降到底。

别把 cnt 当成「左边有几个元素」——相等也加 1，层数会虚高、答案偏大，判断必须卡严格不等。也别看到两个相同的值就以为只算一次，同一层的每个数都得各自降到地面、操作是分开做的，漏掉后一个就会少算。cnt 判层看的是值，累加进答案却按每个元素来。

排完是 [1,2,3,5,5]，9 次怎么加出来

排序后是 [1,2,3,5,5]。最左的 1 是最小值，已经在地面，贡献 0，cnt 还是 0。到 2，它比左邻 1 大，cnt 变 1，2 只需降到 1 走一步，答案加 1 到 1。到 3，比 2 大，cnt 变 2，3 走 3→2→1 两步，答案加 2 到 3。到第一个 5，比 3 大，cnt 变 3，5 走 5→3→2→1 三步，答案加 3 到 6。

到第二个 5，它和左邻 5 相等，cnt 不动、还是 3，但这个 5 同样要降 3 步，答案再加 3，到 9。五个数的贡献依次是 0、1、2、3、3，合起来正好 9 次。

排序之后，答案会不会超出 int

整段时间花在把数排好，排完只从左到右扫一遍、每位一次比较一次累加，合起来 O(n log n)；额外空间只看排序，C++ 和 Java 的排序递归栈是 O(log n)，Python 的 Timsort 最坏要 O(n) 临时缓冲，算法自身只用 ans、cnt 两个计数器。答案最坏出现在所有数两两不同时，总和约 n²/2，本题 n 到五万，约十二亿多，还在 int 的二十一亿以内，三种语言用 int 就够。

Python

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

C++

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

Java

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