Maximize Greatness of an Array
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 to 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
4One optimal rearrangement is
perm = [2, 5, 1, 3, 3, 1, 1], where perm[i] > nums[i] at indices 0, 1, 3, and 4, so the greatness is 4.Example 2
Input
nums = [1,2,3,4]Output
3An optimal rearrangement is
perm = [2, 3, 4, 1], where perm[i] > nums[i] at indices 0, 1, and 2, so the greatness is 3.Constraints
- 1 <= nums.length <= 10^5
- 0 <= nums[i] <= 10^9