3627. 中位数之和的最大值

题目描述

给你一个整数数组 nums，其长度可以被 3 整除。

你需要通过多次操作将数组清空。在每一步操作中，你可以从数组中选择任意三个元素，计算它们的 中位数 ，并将这三个元素从数组中移除。

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

返回通过所有操作得到的 中位数之和的最大值 。

示例 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⁵
nums.length % 3 == 0
1 <= nums[i] <= 10⁹

解法

方法一：贪心 + 排序

为了使得中位数之和最大，我们需要尽可能选择较大的元素作为中位数。由于每次操作只能选择三个元素，因此我们可以将数组排序后，从下标 \(n / 3\) 元素开始，每两个元素选择一个小的，直到数组末尾。这样可以确保我们选择的中位数是最大的。

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

Python3JavaC++GoTypeScript

class Solution:
    def maximumMedianSum(self, nums: List[int]) -> int:
        nums.sort()
        return sum(nums[len(nums) // 3 :: 2])

class Solution {
    public long maximumMedianSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        long ans = 0;
        for (int i = n / 3; i < n; i += 2) {
            ans += nums[i];
        }
        return ans;
    }
}

class Solution {
public:
    long long maximumMedianSum(vector<int>& nums) {
        ranges::sort(nums);
        int n = nums.size();
        long long ans = 0;
        for (int i = n / 3; i < n; i += 2) {
            ans += nums[i];
        }
        return ans;
    }
};

func maximumMedianSum(nums []int) (ans int64) {
    sort.Ints(nums)
    n := len(nums)
    for i := n / 3; i < n; i += 2 {
        ans += int64(nums[i])
    }
    return
}

function maximumMedianSum(nums: number[]): number {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let ans = 0;
    for (let i = n / 3; i < n; i += 2) {
        ans += nums[i];
    }
    return ans;
}

3627. 中位数之和的最大值

题目描述

解法

方法一：贪心 + 排序

评论