刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/largest-values-from-labels
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

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

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

• 子集 s 的大小 小于或等于 numWanted 。
• s 中 最多 有相同标签的 useLimit 项。

一个子集的分数是该子集的值之和。
返回子集 s 的最大分数。

示例 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
解释：选出的子集是第一项和第四项。

提示：

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

思路

看上去挺适合贪心啥的，但其实这个题目没有那么麻烦，先排序，然后用哈希表记录选取次数做为限制条件，按顺序拿数字即可

代码

func largestValsFromLabels(values []int, labels []int, numWanted int, useLimit int) int {
    valuesLen := len(values)
    valueIndex := make([]int, valuesLen)
    for i := 0; i < valuesLen; i++ {
        valueIndex[i] = i
    }
    sort.Slice(valueIndex, func(i, j int) bool {
        return values[valueIndex[i]] > values[valueIndex[j]]
    })

    result, chooseNum := 0, 0
    countMap := make(map[int]int)
    for i := 0; i < valuesLen; i++ {
        if chooseNum == numWanted {
            break
        }

        label := labels[valueIndex[i]]
        if countMap[label] == useLimit {
            continue
        }

        result += values[valueIndex[i]]
        countMap[label]++
        chooseNum++
    }
    return result
}