Medium

题目描述

给你一个下标从 0 开始的整数数组 nums。你可以将 nums 重新排列成一个你选择的新数组 perm。

我们将 nums 的 伟大值 定义为满足 0 <= i < nums.length 且 perm[i] > nums[i] 的下标 i 的数量。

请你返回重新排列 nums 后可以获得的 最大伟大值。

示例 1：

输入：nums = [1,3,5,2,1,3,1]
输出：4
解释：最优重排列之一是 perm = [2,5,1,3,3,1,1]。
在下标 i = 0, 1, 3, 4 处，都有 perm[i] > nums[i]。因此我们返回 4。

示例 2：

输入：nums = [1,2,3,4]
输出：3
解释：最优的重排列是 [2,3,4,1]。
在下标 i = 0, 1, 2 处，都有 perm[i] > nums[i]。因此我们返回 3。

提示：

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9

解题思路

这道题要求我们重新排列数组，使得新数组中尽可能多的位置满足 perm[i] > nums[i]。

核心思路： 为了最大化满足条件的位置数量，我们应该贪心地为每个元素分配一个刚好大于它的最小元素。这样可以避免浪费较大的元素。

算法步骤：

  1. 对原数组进行排序，得到有序的元素序列
  2. 使用双指针技术：
    • left 指针遍历原数组的每个位置
    • right 指针寻找第一个大于 nums[left] 的元素
  3. 如果找到这样的元素，就将其分配给当前位置，两个指针都向前移动
  4. 如果找不到，只移动 left 指针
  5. 统计成功分配的次数即为答案

为什么排序+双指针是最优的？

  • 排序后，我们可以按从小到大的顺序处理元素
  • 对于每个元素，我们总是选择能够满足条件的最小元素，这样可以为后续更大的元素保留更多选择
  • 双指针确保了线性时间复杂度，避免了重复搜索

代码实现

class Solution {
public:
    int maximizeGreatness(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int left = 0, right = 0, count = 0;
        int n = nums.size();
        
        while (left < n && right < n) {
            if (nums[right] > nums[left]) {
                count++;
                left++;
            }
            right++;
        }
        
        return count;
    }
};

class Solution:
    def maximizeGreatness(self, nums: List[int]) -> int:
        nums.sort()
        left = right = count = 0
        n = len(nums)
        
        while left < n and right < n:
            if nums[right] > nums[left]:
                count += 1
                left += 1
            right += 1
        
        return count

public class Solution {
    public int MaximizeGreatness(int[] nums) {
        Array.Sort(nums);
        int left = 0, right = 0, count = 0;
        int n = nums.Length;
        
        while (left < n && right < n) {
            if (nums[right] > nums[left]) {
                count++;
                left++;
            }
            right++;
        }
        
        return count;
    }
}

var maximizeGreatness = function(nums) {
    nums.sort((a, b) => a - b);
    let left = 0, right = 0, count = 0;
    const n = nums.length;
    
    while (left < n && right < n) {
        if (nums[right] > nums[left]) {
            count++;
            left++;
        }
        right++;
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要由排序操作决定，双指针遍历为 O(n)
空间复杂度O(1)只使用常数个额外变量，排序为原地操作

相关题目