一. 题目描述

PS: 该题目正解应该是双指针或二分, 这里提供一种比较新奇的思路——差分

二. 算法

差分

三. 时间复杂度

$O(nlogn)$ 瓶颈是排序的时间复杂度

四. 分析

一开始思路:

将nums数组从大到小排序, 将重复的元素放到数组后,
则前面排完序且两两互不相同的序列长度记为len, 则ans += len - 1; (ans为答案)
接着再对后面重复元素序列重复上述操作, 直至重复元素长度为0或者只有一种数为止.

模拟如下:

nums = [1,3,5,2,1,3,1]
设定左右指针l, r为排序区间
① 排序 1 1 1 2 3 3 5 (l = 0, r = 7)
② 去重 1 2 3 5 1 1 3 (l = 0, r = 7)
③ ans += (4 - 0 - 1)
④ 排序 1 2 3 5 1 1 3 (l = 4, r = 7)
⑤ 去重 1 2 3 4 1 3 1 (l = 4, r = 7)
⑥ ans += (6 - 4 - 1)
⑦ 此时重复元素部分只剩 1 一种数字, 直接break
⑧ 得 ans 为 4

转换思路:

由于unique函数的去重效果并不是将重复元素放至数组后,
而是所有不重复的元素排在数组的最前面，数组末尾未占用的位置保留原来的值.
因此我们只能采取其他方法.
首先我们统计一下每个数出现的次数, 记录在数组arr上,
然后我们可以对arr的进行如下操作:

• 从前往后遍历, 令计数变量cnt = 0;
• 如果某元素出现次数大于等于1, 则我们将其-1, 并且cnt ++;
• ans += cnt - 1
• 如果数组不全为0, 则重复上述操作

可以看到上述操作只是将一开始的思路转化为减去出现次数而已,
而我们统计出现次数后, arr每个元素所对应的nums元素两两互不相同,
由于不同因此一定可以用较大的数去顶替较小的数, 最后剩一个最大没有更大的可以顶替,
利用这点, 我们可以将arr从大到小排序, 而此时上述对arr操作就可以变为:

• 每次选择一段区间, 将区间内的元素-1, 设区间左右端点为l, r
• ans += (r - l)
• 重复上述操作直至所有arr元素为0

对一段区间修改, 我们可以想到差分,(例题: 增减序列) 因此此处我们可以求出arr的差分数组, 对该差分数组的两点进行+1, -1, 即可将某段区间的元素全都减一

五. C++ 代码

class Solution {
public:
    int maximizeGreatness(vector<int>& nums) {
        int ans = 0, len = nums.size();  // 答案, nums的长度
        vector<int> arr;  // 记录每个数出现次数的数组
        // 排序
        sort(nums.begin(), nums.end());
        // 求每个数出现个数
        for(int i = 0; i < len; i ++ )
        {
            int j = i + 1;
            while(j < len && nums[i] == nums[j]) j ++ ;
            int cnt = j - i;
            i = j - 1;
            arr.push_back(cnt);
        }
        // 将arr排序
        sort(arr.begin(), arr.end());
        len = arr.size();  // arr的长度
        // 求arr的差分
        for(int i = len - 1; i > 0; i -- ) arr[i] -= arr[i - 1];
        // 计算将arr变为全0所需的次数
        for(int i = 0; i < len; i ++ )ans += (arr.size() - i - 1) * arr[i];
        return ans;
    }
};