一. 题目描述
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;
}
};