Python 中标签的最大值
pythonserver side programmingprogramming
假设我们有一组项目:第 i 个项目的值为 values[i]，标签为 labels[i]。然后，我们将从这些项目中取一个子集 S，使得 −
- |S| <= num_wanted
- 对于每个标签 L，S 中带有标签 L 的项目数为 <= use_limit。
我们必须找到子集 S 的最大可能和。
例如，如果输入为 values = [5,4,3,2,1] 且标签为 [1,1,2,2,3]、num_wanted = 3、use_limit = 1，则输出将为 9。这是因为在第一、第三和第五个项目中选择了子集。
为了解决这个问题，我们将遵循以下步骤 −
- 创建一个数组 v
- 对于 i，范围为 0 到 values 的长度
- 将 [values[i], labels[i]] 插入 v
- 对 v 进行排序数组
- ans := 0，use := 空映射，并且 i := 0
- 当 num_wanted 和 i < v 的长度
- 如果 v[i, 1] 不存在于 use 映射中
- 将 num_wanted 减少 1
- ans := ans + v[i, 0]
- use[v[i, 1]] := 1
- 否则 use[v[i, 1]] < use_limit
- 将 num_wanted 减少 1
- ans := ans + v[i, 0]
- 将 use[v[i, 1]] 增加 1
- 将 i 增加 1
- 如果 v[i, 1] 不存在于 use 映射中
- 返回 ans
让我们看看下面的实现以便更好地理解 −
示例
class Solution(object):
def largestValsFromLabels(self, values, labels, num_wanted, use_limit):
v = []
for i in range(len(values)):
v.append([values[i],labels[i]])
v = sorted(v,key = lambda v:v[0],reverse=True)
ans = 0
use = {}
i = 0
while num_wanted and i < len(v):
if v[i][1] not in use:
num_wanted -=1
ans+=v[i][0]
use[v[i][1]] = 1
elif use[v[i][1]]<use_limit:
num_wanted -=1
ans+=v[i][0]
use[v[i][1]]+=1
i+=1
return ans
ob = Solution()
print(ob.largestValsFromLabels([5,4,3,2,1],[1,1,2,2,3],3,1))
输入
[5,4,3,2,1] [1,1,2,2,3] 3 1
输出
9
