Question

2592. 最大化数组的伟大值

English Version

题目描述

给你一个下标从 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 <= 105
• 0 <= nums[i] <= 109

解法

方法一：贪心

我们可以先将数组 $nums$ 进行排序。

接下来定义一个指针 $i$，初始时指向数组 $nums$ 的第一个元素。然后遍历数组 $nums$，对于遍历到的每个元素 $x$，如果 $x$ 大于 $nums[i]$，则将指针 $i$ 向右移动一位。

最后返回指针 $i$ 的值即可。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 为数组 $nums$ 的长度。

class Solution:
  def maximizeGreatness(self, nums: List[int]) -> int:
    nums.sort()
    i = 0
    for x in nums:
      i += x > nums[i]
    return i

class Solution {
  public int maximizeGreatness(int[] nums) {
    Arrays.sort(nums);
    int i = 0;
    for (int x : nums) {
      if (x > nums[i]) {
        ++i;
      }
    }
    return i;
  }
}

class Solution {
public:
  int maximizeGreatness(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int i = 0;
    for (int x : nums) {
      i += x > nums[i];
    }
    return i;
  }
};

func maximizeGreatness(nums []int) int {
  sort.Ints(nums)
  i := 0
  for _, x := range nums {
    if x > nums[i] {
      i++
    }
  }
  return i
}

function maximizeGreatness(nums: number[]): number {
  nums.sort((a, b) => a - b);
  let i = 0;
  for (const x of nums) {
    if (x > nums[i]) {
      i += 1;
    }
  }
  return i;
}