受标签影响的最大值

难度: Medium

我们有一个 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 * 10⁴
0 <= values[i], labels[i] <= 2 * 10⁴
1 <= numWanted, useLimit <= n

Submission

运行时间: 35 ms

内存: 20.7 MB

class Solution:
    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:
        pair = [i for i in zip(values, labels)]
        pair.sort()
        cap_dict = dict()
        ans = 0
        num = 0
        for i in range(len(values) - 1, -1, -1):
            if pair[i][1] not in cap_dict:
                cap_dict[pair[i][1]] = 1
                ans += pair[i][0]
                num += 1
            elif cap_dict[pair[i][1]] < useLimit:
                cap_dict[pair[i][1]] += 1
                ans += pair[i][0]
                num += 1
            if num == numWanted:
                return ans
        return ans
        return 0

Explain

此题解的基本思路是首先将元素按照其值进行排序，然后从值最大的元素开始选择，确保不超过每个标签的使用限制 `useLimit` 和总数不超过 `numWanted`。这样可以保证所选的子集有可能是最大值。具体步骤包括： 1. 创建一个包含值和标签对的列表。 2. 将这个列表按值进行排序。 3. 使用一个字典来跟踪每个标签已经使用的次数。 4. 从列表的末尾（值最大的位置）开始，如果当前元素的标签使用次数没有达到 `useLimit`，则将其加入到结果中，并更新标签的使用次数。 5. 检查是否已经选择了 `numWanted` 个元素，如果是，则结束选择。 6. 最后返回所有选中元素值的总和。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:
        # 创建值和标签的配对列表
        pair = [i for i in zip(values, labels)]
        # 按值排序这个列表
        pair.sort()
        # 字典用于跟踪每个标签的使用频率
        cap_dict = dict()
        # 初始化答案和已选择元素的数量
        ans = 0
        num = 0
        # 从值最大的元素开始选择
        for i in range(len(values) - 1, -1, -1):
            # 检查是否可以选择当前元素
            if pair[i][1] not in cap_dict:
                cap_dict[pair[i][1]] = 1
                ans += pair[i][0]
                num += 1
            elif cap_dict[pair[i][1]] < useLimit:
                cap_dict[pair[i][1]] += 1
                ans += pair[i][0]
                num += 1
            # 如果已经选择了足够的元素，则结束循环
            if num == numWanted:
                return ans
        # 返回最大值之和
        return ans

Explore

在算法中，我们使用一个字典`cap_dict`来记录每个标签的使用次数。在考虑是否选择一个元素时，我们首先检查这个元素的标签在`cap_dict`中的计数是否已经达到了`useLimit`。如果未达到，我们才会选择这个元素并增加该标签的使用次数；如果已达到，我们则跳过这个元素，继续检查下一个元素。这样通过`cap_dict`来控制，确保不会超过每个标签的使用限制。

算法首先将所有元素按照值进行排序，无论它们的标签是否相同。在选择元素时，即使几个元素的值相同，它们的标签可能不同，因此它们被视为独立的条目。算法会根据每个元素的标签独立判断是否可以被选中，这意味着即使值相同的不同标签的元素也可以被分别考虑，只要它们的标签的使用次数未达到限制。

在这个问题中，我们的目标是找出值的总和最大的子集。对列表进行排序后，列表末尾的元素是值最大的。从末尾开始迭代可以直接访问这些最大值，这样可以更快地累积较大的值，从而可能达到更高的总和。此方法确保我们首先考虑较大的数值，这是寻找最大值总和子集的一个有效策略。

如果在达到`numWanted`指定的数量之前就遍历完所有元素，算法将会结束迭代并返回当前已选择的元素的值的总和。这意味着最终结果可能不会包含`numWanted`个元素，而是包含了能够在给定的标签使用限制下找到的最大值总和的元素集合。