跳转至

2592. 最大化数组的伟大值

题目描述

给你一个下标从 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

解法

方法一：贪心

思考

排列 \(perm\) 的伟大程度是 \(perm[i]>nums[i]\) 的位置数，求最大值。这是两侧多重集相同的配对，应让较大值去压过尽可能多的较小数。

排序后用双指针：从左到右扫较大候选 \(x\)，若它严格大于当前未被压过的 \(nums[i]\) 则配对成功。能压过的个数即答案。

我们可以先将数组 \(nums\) 进行排序。

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

最后返回指针 \(i\) 的值即可。

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

1
2
3
4
5
6
7
class Solution:
    def maximizeGreatness(self, nums: List[int]) -> int:
        nums.sort()
        i = 0
        for x in nums:
            i += x > nums[i]
        return i

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public int maximizeGreatness(int[] nums) {
        Arrays.sort(nums);
        int i = 0;
        for (int x : nums) {
            if (x > nums[i]) {
                ++i;
            }
        }
        return i;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func maximizeGreatness(nums []int) int {
    sort.Ints(nums)
    i := 0
    for _, x := range nums {
        if x > nums[i] {
            i++
        }
    }
    return i
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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;
}

评论