OJ练习第112题——受标签影响的最大值-Toy模板网

这篇具有很好参考价值的文章主要介绍了OJ练习第112题——受标签影响的最大值。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

受标签影响的最大值

力扣链接：1090. 受标签影响的最大值

题目描述

我们有一个 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
解释：选出的子集是第一项，第二项和第三项。

Java代码

class Solution {
    public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
        int count[] = new int[20001], n = labels.length;
        Integer index[] = new Integer[n];
        for(int i = 0; i < n; i++) {
            index[i] = i;
        }
        Arrays.sort(index, (a, b) -> values[b] - values[a]);
        int res = 0;
        for(int i = 0; i < n && numWanted > 0; i++, numWanted--) {
            while(i < n && count[labels[index[i]]] >= useLimit) i++;
            if(i < n) {
                res += values[index[i]];
                count[labels[index[i]]]++;
            }
        }
        return res;
    }
}

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

到了这里，关于OJ练习第112题——受标签影响的最大值的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！