class Solution {
public:
int maximizeGreatness(vector<int>& nums) {
}
};
6324. 最大化数组的伟大值
给你一个下标从 0 开始的整数数组 nums 。你需要将 nums 重新排列成一个新的数组 perm 。
定义 nums 的 伟大值 为满足 0 <= i < nums.length 且 perm[i] > nums[i] 的下标数目。
请你返回重新排列 nums 后的 最大 伟大值。
示例 1：
输入：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 。
示例 2：
输入：nums = [1,2,3,4] 输出：3 解释：最优排列为 [2,3,4,1] 。 在下标为 0, 1 和 2 处，都有 perm[i] > nums[i] 。因此我们返回 3 。
提示：
1 <= nums.length <= 1050 <= nums[i] <= 109原站题解
golang 解法, 执行用时: 104 ms, 内存消耗: 12.7 MB, 提交时间: 2023-03-19 22:05:07
func maximizeGreatness(nums []int) int {
maxCnt := 0
cnt := map[int]int{}
for _, v := range nums {
cnt[v]++
maxCnt = max(maxCnt, cnt[v])
}
return len(nums) - maxCnt
}
func max(a, b int) int { if a < b { return b }; return a }
cpp 解法, 执行用时: 128 ms, 内存消耗: 92.7 MB, 提交时间: 2023-03-19 22:04:55
class Solution {
public:
int maximizeGreatness(vector<int> &nums) {
int mx = 0;
unordered_map<int, int> cnt;
for (int x : nums)
mx = max(mx, ++cnt[x]);
return nums.size() - mx;
}
};
java 解法, 执行用时: 20 ms, 内存消耗: 57.3 MB, 提交时间: 2023-03-19 22:04:39
class Solution {
public int maximizeGreatness(int[] nums) {
int mx = 0;
var cnt = new HashMap<Integer, Integer>();
for (int x : nums)
mx = Math.max(mx, cnt.merge(x, 1, Integer::sum));
return nums.length - mx;
}
}
python3 解法, 执行用时: 72 ms, 内存消耗: 34.4 MB, 提交时间: 2023-03-19 22:04:18
class Solution:
def maximizeGreatness(self, nums: List[int]) -> int:
return len(nums) - max(Counter(nums).values())
golang 解法, 执行用时: 104 ms, 内存消耗: 8.3 MB, 提交时间: 2023-03-19 22:03:39
func maximizeGreatness(nums []int) (i int) {
sort.Ints(nums)
for _, x := range nums {
if x > nums[i] {
i++
}
}
return
}
cpp 解法, 执行用时: 152 ms, 内存消耗: 73.9 MB, 提交时间: 2023-03-19 22:03:22
class Solution {
public:
int maximizeGreatness(vector<int> &nums) {
sort(nums.begin(), nums.end());
int i = 0;
for (int x : nums)
if (x > nums[i])
++i;
return i;
}
};
java 解法, 执行用时: 9 ms, 内存消耗: 56.3 MB, 提交时间: 2023-03-19 22:03:10
class Solution {
public int maximizeGreatness(int[] nums) {
Arrays.sort(nums);
int i = 0;
for (int x : nums)
if (x > nums[i])
++i;
return i;
}
}
python3 解法, 执行用时: 72 ms, 内存消耗: 28.6 MB, 提交时间: 2023-03-19 22:02:59
# 贪心 + 排序 + 双指针
class Solution:
def maximizeGreatness(self, nums: List[int]) -> int:
nums.sort()
i = 0
for x in nums:
if x > nums[i]:
i += 1
return i