题目描述

受标签影响的最大值

我们有一个 n 项的集合。给出两个整数数组 values 和labels ，第 i 个元素的值和标签分别是 values[i] 和 labels[i]。还会给出两个整数 numWanted 和 useLimit 。

从 n 个元素中选择一个子集 s :

• 子集 s 的大小 小于或等于 numWanted 。
• s 中 最多 有相同标签的 useLimit 项 —— 比如useLimit为2，则最多取两个label相同的数
• 一个子集的 分数 是该子集的值之和。

返回子集 s 的最大分数 。

提示：

n == values.length == labels.length 1 <= n <= 2 * 104 0 <= values[i], labels[i] <= 2 * 10^4 1 <= numWanted, useLimit <= n

测试用例

用例1

• 输入：values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1
• 输出：9
• 解释：选出的子集是第一项，第三项和第五项。

用例2

• 输入：values = [5,4,3,2,1], labels = [1,3,3,3,2], numWanted = 3, useLimit = 2
• 输出：12
• 解释：选出的子集是第一项，第二项和第三项。

用例3

• 输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], numWanted = 3, useLimit = 1
• 输出：16
• 解释：选出的子集是第一项和第四项。

思路

我们首先将元素按照 values 的值进行降序排序。待排序完成后，我们依次遍历每个元素并判断是否选择。我们可以使用一个变量 choose记录已经选择的元素个数，以及一个哈希表记录每一种标签已经选择的元素个数（键表示标签，值表示该标签已经选择的元素个数）：

如果 choose=numWanted，我们可以直接退出遍历；

如果当前元素的标签在哈希表中对应的值等于 useLimit，我们忽略这个元素，否则我们选择这个元素，并更新 choose、哈希表以及答案。

细节

由于题目中的 values 和 labels 是分成两个数组给出的，直接排序会比较困难。我们可以额外开辟一个同样长度为 n 的数组，存储下标，并直接在该数组上进行排序即可

💪 代码实现

// v8输入

var __readline = require("readline-sync");
__readline.setDefaultOptions({ prompt: "" });

var readline = __readline.prompt;

console.log("请输入values: ");
let values = [];

let line1 = readline().split(" ").map(Number);

for (let i = 0; i < line1.length; i++) {
  values.push(line1[i]);
}

console.log("请输入labels: ");

let labels = [];

let line2 = readline().split(" ").map(Number);

for (let i = 0; i < line2.length; i++) {
  labels.push(line2[i]);
}
console.log("请输入numWanted: ");
let numWanted = readline();
console.log("请输入useLimit: ");
let useLimit = readline();

// 算法
/**
 * @param {number[]} values
 * @param {number[]} labels
 * @param {number} numWanted
 * @param {number} useLimit
 * @return {number}
 */
var largestValsFromLabels = function (values, labels, numWanted, useLimit) {
  const n = values.length;
  const idx = Array.from(Array(n), (_, i) => i);
  idx.sort((i, j) => values[j] - values[i]);

  let ans = 0,
    choose = 0;
  // cnt记录 {label , 次数}
  const cnt = {};
  for (let i = 0; i < n; i++) {
    const label = labels[idx[i]];
    // 记录当前元素的label

    // label与useLimit比较
    if (cnt[label] == useLimit) {
      continue;
    }
    choose++;
    ans += values[idx[i]];
    cnt[label] = (cnt[label] || 0) + 1;
    if (choose == numWanted) {
      break;
    }
  }

  return ans;
};

console.log(
  "结果为： ",
  largestValsFromLabels(values, labels, numWanted, useLimit)
);