Skip to content

Latest commit

 

History

History
142 lines (86 loc) · 3.75 KB

2592.maximize-greatness-of-an-array.md

File metadata and controls

142 lines (86 loc) · 3.75 KB

题目地址(2592. 最大化数组的伟大值)

https://leetcode.cn/problems/maximize-greatness-of-an-array/

题目描述

给你一个下标从 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 进行一次排序。接下来是重点,如果 nums 的伟大值是 k,那么排序后的 nums 的前 k 大的数一定比前 k 小的数都大。

注意我们比较前 k 大和 前 k 小的数时候要用反田忌赛马思想,即用前 k 大的中最小的和前 k 小的最小的比较。具体看下方代码实现。

不会二分的看下仓库的二分专题,里面有讲解+模板。

接下来就是套最右二分模板即可。

关键点

  • 能力检测二分

代码

  • 语言支持:Python3

Python3 Code:

class Solution:
    def maximizeGreatness(self, nums: List[int]) -> int:
        A = sorted(nums)

        l, r = 1, len(nums)
        def can(mid):
            for i in range(mid):
                if A[i] >= A[len(nums) - mid + i]: return False
            return True


        while l <= r:
            mid = (l + r) // 2
            if can(mid):
                l = mid + 1
            else:
                r = mid - 1
        return r

复杂度分析

令 n 为数组长度。

  • 时间复杂度:$O(nlogn)$
  • 空间复杂度:不确定,取决于内置的排序算法

贪心

思路

还有一种性能更加好的做法。还是先排序,接下来用一个指针 i 记录”被比下去的数字“,显然我们要贪心地选择尽可能小的数字,因此他们更容易被比下去,而且其和较大的数贡献都是一样的(都是使得伟大值增加 1)。

接下来,我们需要选择谁把这些数字”比下去“,同样我们用尽可能小的数,这样留下较大的数字才更有可能将其他数字”比下去“。

代码

  • 语言支持:Python3

Python3 Code:

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

复杂度分析

令 n 为数组长度。

  • 时间复杂度:$O(nlogn)$
  • 空间复杂度:不确定,取决于内置的排序算法

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。