largest-values-from-labels

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given <code>n</code> item&#39;s value and label as two integer arrays <code>values</code> and <code>labels</code>. You are also given two integers <code>numWanted</code> and <code>useLimit</code>.

Your task is to find a subset of items with the maximum sum of their values such that:

<ul>
	<li>The number of items is at most <code>numWanted</code>.</li>
	<li>The number of items with the same label is at most <code>useLimit</code>.</li>
</ul>

Return the maximum sum.

&nbsp;
Example 1:

<div class="example-block">
Input: values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1

Output: 9

Explanation:

The subset chosen is the first, third, and fifth items with the sum of values 5 + 3 + 1.
</div>

Example 2:

<div class="example-block">
Input: values = [5,4,3,2,1], labels = [1,3,3,3,2], numWanted = 3, useLimit = 2

Output: 12

Explanation:

The subset chosen is the first, second, and third items with the sum of values 5 + 4 + 3.
</div>

Example 3:

<div class="example-block">
Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], numWanted = 3, useLimit = 1

Output: 16

Explanation:

The subset chosen is the first and fourth items with the sum of values 9 + 7.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>n == values.length == labels.length</code></li>
	<li><code>1 &lt;= n &lt;= 2 * 104</code></li>
	<li><code>0 &lt;= values[i], labels[i] &lt;= 2 * 104</code></li>
	<li><code>1 &lt;= numWanted, useLimit &lt;= n</code></li>
</ul>

largestValsFromLabels

Largest Values From Labels

Greedy

Array

Hash Table

Counting

Sorting

以两个整数数组 &nbsp;<code>values</code>&nbsp;和 <code>labels</code>&nbsp;给定&nbsp;<code>n</code>&nbsp;个项的值和标签，并且给出两个整数&nbsp;<code>numWanted</code>&nbsp;和 <code>useLimit</code> 。

你的任务是从这些项中找到一个值的和 最大 的子集使得：

<ul>
	<li>项的数量 最多 为&nbsp;<code>numWanted</code>。</li>
	<li>相同标签的项的数量&nbsp;最多 为&nbsp;<code>useLimit</code>。</li>
</ul>

返回最大的和。

&nbsp;

示例 1：

<div class="example-block">
输入：values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1

输出：9

解释：

选择的子集是第一个、第三个和第五个项，其值之和为 5 + 3 + 1。
</div>

示例 2：

<div class="example-block">
输入：values = [5,4,3,2,1], labels = [1,3,3,3,2], numWanted = 3, useLimit = 2

输出：12

解释：

选择的子集是第一个、第二个和第三个项，其值之和为 5 + 4 + 3。
</div>

示例 3：

<div class="example-block">
输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], numWanted = 3, useLimit = 1

输出：16

解释：

选择的子集是第一个和第四个项，其值之和为 9 + 7。
</div>

&nbsp;

提示：

<ul>
	<li><code>n == values.length == labels.length</code></li>
	<li><code>1 &lt;= n &lt;= 2 * 104</code></li>
	<li><code>0 &lt;= values[i], labels[i] &lt;= 2 * 104</code></li>
	<li><code>1 &lt;= numWanted, useLimit &lt;= n</code></li>
</ul>