Question

2592. Maximize Greatness of an Array

中文文档

Description

You are given a 0-indexed integer array nums. You are allowed to permute nums into a new array perm of your choosing.

We define the greatness of nums be the number of indices 0 <= i < nums.length for which perm[i] > nums[i].

Return _the maximum possible greatness you can achieve after permuting_ nums.

 

Example 1:

Input: nums = [1,3,5,2,1,3,1]
Output: 4
Explanation: One of the optimal rearrangements is perm = [2,5,1,3,3,1,1].
At indices = 0, 1, 3, and 4, perm[i] > nums[i]. Hence, we return 4.

Example 2:

Input: nums = [1,2,3,4]
Output: 3
Explanation: We can prove the optimal perm is [2,3,4,1].
At indices = 0, 1, and 2, perm[i] > nums[i]. Hence, we return 3.

 

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109

Solutions

Solution 1: Greedy

We can sort the array $nums$ first.

Then we define a pointer $i$ pointing to the first element of the array $nums$. We traverse the array $nums$, and for each element $x$ we encounter, if $x$ is greater than $nums[i]$, then we move the pointer $i$ to the right.

Finally, we return the value of the pointer $i$.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(\log n)$, where $n$ is the length of the array $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;
}