1090.受标签影响的最大值.md

1090.受标签影响的最大值

/*
 * @lc app=leetcode.cn id=1090 lang=typescript
 *
 * [1090] 受标签影响的最大值
 */

// @lc code=start
function largestValsFromLabels(values: number[], labels: number[], numWanted: number, useLimit: number): number {}
// @lc code=end

解法 1: 哈希表+排序

function largestValsFromLabels(values: number[], labels: number[], numWanted: number, useLimit: number): number {
  const map = new Map<number, number[]>()
  for (let i = 0; i < values.length; i++) {
    const a = labels[i],
      b = values[i]
    if (!map.has(a)) map.set(a, [])
    map.get(a).push(b)
  }
  const nums: number[] = []
  for (let [, arr] of map) {
    arr.sort((a, b) => b - a)
    for (let i = 0; i < useLimit && i < arr.length; i++) {
      nums.push(arr[i])
    }
  }
  nums.sort((a, b) => b - a)
  let res = 0
  for (let i = 0; i < numWanted && i < nums.length; i++) {
    res += nums[i]
  }
  return res
}

Case

test.each([
  { input: { values: [5, 4, 3, 2, 1], labels: [1, 1, 2, 2, 3], numWanted: 3, useLimit: 1 }, output: 9 },
  { input: { values: [5, 4, 3, 2, 1], labels: [1, 3, 3, 3, 2], numWanted: 3, useLimit: 2 }, output: 12 },
  { input: { values: [9, 8, 8, 7, 6], labels: [0, 0, 0, 1, 1], numWanted: 3, useLimit: 1 }, output: 16 },
])(
  'input: values = $input.values, labels = $input.labels, numWanted = $input.numWanted, useLimit = $input.useLimit',
  ({ input: { values, labels, numWanted, useLimit }, output }) => {
    expect(largestValsFromLabels(values, labels, numWanted, useLimit)).toEqual(output)
  },
)