maximum-median-sum-of-subsequences-of-size-3

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given an integer array <code>nums</code> with a length divisible by 3.

You want to make the array empty in steps. In each step, you can select any three elements from the array, compute their median, and remove the selected elements from the array.

The median of an odd-length sequence is defined as the middle element of the sequence when it is sorted in non-decreasing order.

Return the maximum possible sum of the medians computed from the selected elements.

&nbsp;
Example 1:

<div class="example-block">
Input: nums = [2,1,3,2,1,3]

Output: 5

Explanation:

<ul>
	<li>In the first step, select elements at indices 2, 4, and 5, which have a median 3. After removing these elements, <code>nums</code> becomes <code>[2, 1, 2]</code>.</li>
	<li>In the second step, select elements at indices 0, 1, and 2, which have a median 2. After removing these elements, <code>nums</code> becomes empty.</li>
</ul>

Hence, the sum of the medians is <code>3 + 2 = 5</code>.
</div>

Example 2:

<div class="example-block">
Input: nums = [1,1,10,10,10,10]

Output: 20

Explanation:

<ul>
	<li>In the first step, select elements at indices 0, 2, and 3, which have a median 10. After removing these elements, <code>nums</code> becomes <code>[1, 10, 10]</code>.</li>
	<li>In the second step, select elements at indices 0, 1, and 2, which have a median 10. After removing these elements, <code>nums</code> becomes empty.</li>
</ul>

Hence, the sum of the medians is <code>10 + 10 = 20</code>.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 5 * 105</code></li>
	<li><code>nums.length % 3 == 0</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
</ul>

第 460 场周赛

weekly-contest-460

maximumMedianSum

高级工程师

Maximum Median Sum of Subsequences of Size 3

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

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

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

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

&nbsp;

示例 1：

<div class="example-block">
输入： nums = [2,1,3,2,1,3]

输出： 5

解释：

<ul>
	<li>第一步，选择下标为 2、4 和 5 的元素，它们的中位数是 3。移除这些元素后，<code>nums</code> 变为 <code>[2, 1, 2]</code>。</li>
	<li>第二步，选择下标为 0、1 和 2 的元素，它们的中位数是 2。移除这些元素后，<code>nums</code> 变为空数组。</li>
</ul>

因此，中位数之和为 <code>3 + 2 = 5</code>。
</div>

示例 2：

<div class="example-block">
输入： nums = [1,1,10,10,10,10]

输出： 20

解释：

<ul>
	<li>第一步，选择下标为 0、2 和 3 的元素，它们的中位数是 10。移除这些元素后，<code>nums</code> 变为 <code>[1, 10, 10]</code>。</li>
	<li>第二步，选择下标为 0、1 和 2 的元素，它们的中位数是 10。移除这些元素后，<code>nums</code> 变为空数组。</li>
</ul>

因此，中位数之和为 <code>10 + 10 = 20</code>。
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 5 * 105</code></li>
	<li><code>nums.length % 3 == 0</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
</ul>