Medium

题目描述

给定一个长度能被3整除的整数数组 nums。

你想要通过步骤将数组变为空。在每一步中，你可以从数组中选择任意三个元素，计算它们的中位数，然后从数组中移除这些选中的元素。

奇数长度序列的中位数定义为按非递减顺序排序时序列的中间元素。

返回从选中元素计算出的中位数的最大可能和。

示例 1:

输入: nums = [2,1,3,2,1,3]
输出: 5

解释:
- 第一步，选择索引 2、4、5 的元素，中位数为 3。移除这些元素后，nums 变为 [2, 1, 2]。
- 第二步，选择索引 0、1、2 的元素，中位数为 2。移除这些元素后，nums 变为空。

因此中位数之和为 3 + 2 = 5。

示例 2:

输入: nums = [1,1,10,10,10,10]
输出: 20

解释:
- 第一步，选择索引 0、2、3 的元素，中位数为 10。移除这些元素后，nums 变为 [1, 10, 10]。
- 第二步，选择索引 0、1、2 的元素，中位数为 10。移除这些元素后，nums 变为空。

因此中位数之和为 10 + 10 = 20。

约束条件:

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

提示:

  • 对 nums 中的值进行排序
  • 重复选择最大的2个值和最小值

解题思路

这道题的核心思路是贪心策略。我们要最大化每次选择三个元素的中位数之和。

首先分析什么情况下能得到最大的中位数：

  • 对于三个元素 a ≤ b ≤ c，中位数是 b
  • 为了让中位数尽可能大，我们希望 b 尽可能大
  • 但同时我们需要至少有一个元素 ≤ b 和一个元素 ≥ b

根据提示，最优策略是：

  1. 将数组排序
  2. 每次选择最小的一个元素和最大的两个元素
  3. 这样中位数就是次大的那个元素

为什么这个策略是最优的？

  • 排序后，假设数组为 [a1, a2, ..., an]
  • 每次选择 a1（最小）, an（最大）, an-1（次大）
  • 中位数是 an-1，这是当前能获得的最大中位数
  • 移除这三个元素后，剩余元素仍然有序，可以继续应用相同策略

这个贪心策略的正确性在于：我们总是在当前状态下选择能产生最大中位数的组合，而不会影响后续选择的最优性。

代码实现

class Solution {
public:
    long long maximumMedianSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        
        long long sum = 0;
        int n = nums.size();
        
        for (int i = 0; i < n / 3; i++) {
            // 选择最小值nums[i]和最大的两个值nums[n-1-2*i], nums[n-2-2*i]
            // 中位数是次大的值
            sum += nums[n - 2 - 2 * i];
        }
        
        return sum;
    }
};

class Solution:
    def maximumMedianSum(self, nums: List[int]) -> int:
        nums.sort()
        
        total = 0
        n = len(nums)
        
        for i in range(n // 3):
            # 选择最小值nums[i]和最大的两个值nums[n-1-2*i], nums[n-2-2*i]
            # 中位数是次大的值
            total += nums[n - 2 - 2 * i]
        
        return total

public class Solution {
    public long MaximumMedianSum(int[] nums) {
        Array.Sort(nums);
        
        long sum = 0;
        int n = nums.Length;
        
        for (int i = 0; i < n / 3; i++) {
            // 选择最小值nums[i]和最大的两个值nums[n-1-2*i], nums[n-2-2*i]
            // 中位数是次大的值
            sum += nums[n - 2 - 2 * i];
        }
        
        return sum;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumMedianSum = function(nums) {
    nums.sort((a, b) => a - b);
    
    let sum = 0;
    const n = nums.length;
    
    for (let i = 0; i < n / 3; i++) {
        // 选择最小值nums[i]和最大的两个值nums[n-1-2*i], nums[n-2-2*i]
        // 中位数是次大的值
        sum += nums[n - 2 - 2 * i];
    }
    
    return sum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
排序O(n log n)O(1)
计算中位数和O(n)O(1)
总计O(n log n)O(1)

其中 n 为数组 nums 的长度。空间复杂度为 O(1)，因为只使用了常数额外空间（原地排序）。