题目描述
给你一个下标从 0 开始的整数数组 nums
。你需要将 nums
重新排列成一个新的数组 perm
。
定义 nums
的 伟大值 为满足 0 <= i < nums.length
且 perm[i] > nums[i]
的下标数目。
请你返回重新排列 nums
后的 最大 伟大值。
样例
输入:nums = [1,3,5,2,1,3,1]
输出:4
解释:一个最优安排方案为 perm = [2,5,1,3,3,1,1]。
在下标为 0, 1, 3 和 4 处,都有 perm[i] > nums[i]。因此我们返回 4。
输入:nums = [1,2,3,4]
输出:3
解释:最优排列为 [2,3,4,1]。
在下标为 0, 1 和 2 处,都有 perm[i] > nums[i]。因此我们返回 3。
限制
1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9
算法
(贪心,排序) $O(n \log n)$
- 将数组从小到大排序,维护双指针 $i$ 和 $j$,初始时为 $0$。
- 对应每个位置 $i$,找到最小的位置 $j$,满足 $nums(j) > nums(i)$,然后再移动 $j$。如果能找到 $j$,则答案加 $1$。如果过程中 $j \ge n$,则结束。
时间复杂度
- 排序的时间复杂度为 $O(n \log n)$。
- 排序后,每个位置最多遍历两次,故总时间复杂度为 $O(n \log n)$。
空间复杂度
- 需要 $O(\log n)$ 的额外空间存储排序的系统栈。
C++ 代码
class Solution {
public:
int maximizeGreatness(vector<int>& nums) {
const int n = nums.size();
sort(nums.begin(), nums.end());
int ans = 0;
for (int i = 0, j = 0; i < n; i++) {
while (j < n && nums[j] <= nums[i])
j++;
if (j == n)
break;
ans++;
j++;
}
return ans;
}
};