LeetCode 题解工作台
中位数之和的最大值
给你一个整数数组 nums ，其长度可以被 3 整除。 你需要通过多次操作将数组清空。在每一步操作中，你可以从数组中选择任意三个元素，计算它们的 中位数 ，并将这三个元素从数组中移除。 奇数长度数组的 中位数 定义为数组按非递减顺序排序后位于中间的元素。 返回通过所有操作得到的 中位数之和的最大值 …
0
题型
5
代码语言
0
相关题
当前训练重点
中等 · maximum·median·求和·of·subsequences·of·size·3·core·interview·pattern
答案摘要
为了使得中位数之和最大，我们需要尽可能选择较大的元素作为中位数。由于每次操作只能选择三个元素，因此我们可以将数组排序后，从下标 $n / 3$ 元素开始，每两个元素选择一个小的，直到数组末尾。这样可以确保我们选择的中位数是最大的。 时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 是数组 的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 maximum·median·求和·of·subsequences·of·size·3·core·interview·pattern 题型思路
题目描述
给你一个整数数组 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 * 105nums.length % 3 == 01 <= nums[i] <= 109
解题思路
方法一：贪心 + 排序
为了使得中位数之和最大，我们需要尽可能选择较大的元素作为中位数。由于每次操作只能选择三个元素，因此我们可以将数组排序后，从下标 元素开始，每两个元素选择一个小的，直到数组末尾。这样可以确保我们选择的中位数是最大的。
时间复杂度 ，空间复杂度 。其中 是数组 的长度。
class Solution:
def maximumMedianSum(self, nums: List[int]) -> int:
nums.sort()
return sum(nums[len(nums) // 3 :: 2])
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Understanding of sorting and its impact on selecting medians
- question_mark
Ability to apply greedy strategies for optimization
- question_mark
Familiarity with common patterns in subsequence problems
常见陷阱
外企场景- error
Incorrect median calculation for subsequences
- error
Not sorting the array before selection
- error
Failing to use a greedy approach to maximize the sum of medians
进阶变体
外企场景- arrow_right_alt
Using a different subsequence size
- arrow_right_alt
Minimizing the sum of medians instead of maximizing
- arrow_right_alt
Allowing duplicates in the array for varied subsequence selections