1090.受标签影响的最大值

链接：1090.受标签影响的最大值
难度：Medium
标签：贪心、数组、哈希表、计数、排序
简介：返回子集 s 的最大 分数 。

题解 1 - cpp

• 编辑时间：2023-05-23
• 执行用时：44ms
• 内存消耗：22.2MB
• 编程语言：cpp
• 解法介绍：利用堆找出最大的值贪心塞入。

class Solution {
public:
    int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {
        unordered_map<int, vector<int>> m;
        unordered_map<int, int> mcnt;
        int n = values.size();
        for (int i = 0; i < n; i++) m[labels[i]].push_back(values[i]);
        for (auto &item : m) sort(item.second.begin(), item.second.end());
        auto cmp = [&](int x, int y) -> bool { return m[x].back() < m[y].back(); };
        priority_queue<int, vector<int>, decltype(cmp)> q(cmp);
        for (auto &item : m) q.push(item.first);
        int res = 0;
        for (int i = 0; i < numWanted && q.size(); i++) {
            int idx = q.top();
            q.pop();
            res += m[idx].back();
            m[idx].pop_back();
            if (++mcnt[idx] < useLimit && m[idx].size()) q.push(idx);
        }
        return res;
    }
};

题解 2 - cpp

• 编辑时间：2023-05-23
• 执行用时：52ms
• 内存消耗：19.3MB
• 编程语言：cpp
• 解法介绍：排序后从后往前遍历。

class Solution {
public:
    int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {
        int n = values.size();
        vector<int> list;
        for (int i = 0; i < n; i++) list.push_back(i);
        sort(list.begin(), list.end(), [&](auto &i1, auto &i2) {
            return values[i1] < values[i2];
        });
        unordered_map<int, int> m;
        int res = 0;
        for (int i = n - 1, cnt = 0; i >= 0 && cnt < numWanted; i--) {
            if (m[labels[list[i]]] == useLimit) continue;
            m[labels[list[i]]] += 1;
            res += values[list[i]];
            cnt += 1;
        }
        return res;
    }
};

题解 3 - python

• 编辑时间：2023-05-23
• 执行用时：60ms
• 内存消耗：19.8MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:
        n = len(values)
        list = [i for i in range(n)]
        list.sort(key=lambda i: values[i])
        m = Counter()
        res = 0
        cnt = 0
        for i in range(n-1, -1, -1):
            if cnt >= numWanted:
                break
            if m[labels[list[i]]] == useLimit:
                continue
            m[labels[list[i]]] += 1
            res += values[list[i]]
            cnt += 1
        return res

题解 4 - rust

• 编辑时间：2023-05-23
• 执行用时：4ms
• 内存消耗：2.6MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
pub fn largest_vals_from_labels(
    values: Vec<i32>,
    labels: Vec<i32>,
    num_wanted: i32,
    use_limit: i32,
) -> i32 {
    let n = values.len();
    let mut list = vec![];
    for i in 0..n {
        list.push(i);
    }
    list.sort_by_key(|i| values[*i]);
    let mut m = std::collections::HashMap::<i32, i32>::new();
    let mut res = 0;
    let mut cnt = 0;
    for i in (0..n).rev() {
        if cnt >= num_wanted {
            break;
        }
        let item = m.entry(labels[list[i]]).or_insert(0);
        if *item < use_limit {
            *item += 1;
            res += values[list[i]];
            cnt += 1;
        }
    }
    res
}
}