贪心题目:受标签影响的最大值

文章目录

  • 题目
    • 标题和出处
    • 难度
    • 题目描述
      • 要求
      • 示例
      • 数据范围
  • 解法
    • 思路和算法
    • 代码
    • 复杂度分析

题目

标题和出处

标题:受标签影响的最大值

出处:1090. 受标签影响的最大值

难度

5 级

题目描述

要求

有一个n \texttt{n}n项的集合。给定两个整数数组values \texttt{values}values和labels \texttt{labels}labels,第i \texttt{i}i个元素的值和标签分别是values[i] \texttt{values[i]}values[i]和labels[i] \texttt{labels[i]}labels[i]。另外给定两个整数numWanted \texttt{numWanted}numWanted和useLimit \texttt{useLimit}useLimit。

从n \texttt{n}n个元素中选择一个符合下列要求的子集s \texttt{s}s:

  • 子集s \texttt{s}s的大小小于或等于numWanted \texttt{numWanted}numWanted。
  • 子集s \texttt{s}s中的相同标签的元素最多有useLimit \texttt{useLimit}useLimit个。

一个子集的分数是该子集的值之和。

返回子集s \texttt{s}s的最大分数。

示例

示例 1:

输入:values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1 \texttt{values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1}values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1
输出:9 \texttt{9}9
解释:选出的子集是第一项、第三项和第五项。

示例 2:

输入:values = [5,4,3,2,1], labels = [1,3,3,3,2], numWanted = 3, useLimit = 2 \texttt{values = [5,4,3,2,1], labels = [1,3,3,3,2], numWanted = 3, useLimit = 2}values = [5,4,3,2,1], labels = [1,3,3,3,2], numWanted = 3, useLimit = 2
输出:12 \texttt{12}12
解释:选出的子集是第一项、第二项和第三项。

示例 3:

输入:values = [9,8,8,7,6], labels = [0,0,0,1,1], numWanted = 3, useLimit = 1 \texttt{values = [9,8,8,7,6], labels = [0,0,0,1,1], numWanted = 3, useLimit = 1}values = [9,8,8,7,6], labels = [0,0,0,1,1], numWanted = 3, useLimit = 1
输出:16 \texttt{16}16
解释:选出的子集是第一项和第四项。

数据范围

  • n = values.length = labels.length \texttt{n} = \texttt{values.length} = \texttt{labels.length}n=values.length=labels.length
  • 1 ≤ n ≤ 2 × 10 4 \texttt{1} \le \texttt{n} \le \texttt{2} \times \texttt{10}^\texttt{4}1≤n≤2×104
  • 0 ≤ values[i], labels[i] ≤ 2 × 10 4 \texttt{0} \le \texttt{values[i], labels[i]} \le \texttt{2} \times \texttt{10}^\texttt{4}0≤values[i], labels[i]≤2×104
  • 1 ≤ numWanted, useLimit ≤ n \texttt{1} \le \texttt{numWanted, useLimit} \le \texttt{n}1≤numWanted, useLimit≤n

解法

思路和算法

为了得到所选子集的最大分数,可以使用贪心策略。

由于所有的元素值都是非负整数,当子集的元素个数小于numWanted \textit{numWanted}numWanted时,在不违反规则的情况下将一个新元素加入子集之后,子集的分数一定会增加或不变,不可能减少,因此应该在不违反规则的情况下将尽可能多的元素加入子集。

如果没有相同标签的元素最多useLimit \textit{useLimit}useLimit个的限制,则应该选值最大的numWanted \textit{numWanted}numWanted个元素加入子集,此时子集的分数最大,如果将其中的任意元素换成更小的元素,则子集的分数不会增加,只会减少。在有标签限制的情况下,如果同一个标签的元素个数超过useLimit \textit{useLimit}useLimit,则不能选该标签的所有元素,根据贪心策略,在限定可选元素个数上限的情况下,应选值最大的元素,否则子集的分数不可能更大。

为了按照从大到小的顺序选取元素,同时保留每个元素对应的标签信息,需要创建二维数组记录元素值与标签,将二维数组按照元素值降序排序。遍历排序后的数组,使用哈希表记录每个标签下选取的元素个数,对于每个元素,得到元素的值与标签,执行如下操作。

  • 如果当前标签下选取的元素个数已经达到useLimit \textit{useLimit}useLimit,则跳过该元素。

  • 如果当前标签下选取的元素个数小于useLimit \textit{useLimit}useLimit,则选取当前元素,将元素值加到子集的分数,将当前标签下选取的元素个数加1 11,将numWanted \textit{numWanted}numWanted减1 11。

当遍历结束或者numWanted \textit{numWanted}numWanted减少到0 00时,结束操作,此时即可得到子集的最大分数。

代码

classSolution{publicintlargestValsFromLabels(int[]values,int[]labels,intnumWanted,intuseLimit){intmaxScore=0;intn=values.length;int[][]valuesLabels=newint[n][2];for(inti=0;i<n;i++){valuesLabels[i][0]=values[i];valuesLabels[i][1]=labels[i];}Arrays.sort(valuesLabels,(a,b)->b[0]-a[0]);Map<Integer,Integer>labelCounts=newHashMap<Integer,Integer>();for(inti=0;i<n&&numWanted>0;i++){intvalue=valuesLabels[i][0],label=valuesLabels[i][1];intcount=labelCounts.getOrDefault(label,0);if(count<useLimit){maxScore+=value;labelCounts.put(label,count+1);numWanted--;}}returnmaxScore;}}

复杂度分析

  • 时间复杂度:O ( n log ⁡ n ) O(n \log n)O(nlogn),其中n nn是数组values \textit{values}values和labels \textit{labels}labels的长度。创建二维数组需要O ( n ) O(n)O(n)的时间,排序需要O ( n log ⁡ n ) O(n \log n)O(nlogn)的时间,排序之后遍历二维数组需要O ( n ) O(n)O(n)的时间,因此时间复杂度是O ( n log ⁡ n ) O(n \log n)O(nlogn)。

  • 空间复杂度:O ( n ) O(n)O(n),其中n nn是数组values \textit{values}values和labels \textit{labels}labels的长度。二维数组和哈希表需要O ( n ) O(n)O(n)的空间。

相关新闻

【漏洞修复】 CVE Linux 系统应用漏洞修复笔记

【漏洞修复】 CVE Linux 系统应用漏洞修复笔记

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/11/19 9:15:38 阅读更多 →
基于Python+MySQL的员工档案管理系统

基于Python+MySQL的员工档案管理系统

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/11/11 15:11:34 阅读更多 →
什么是GC

什么是GC

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/11/4 6:35:59 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年&#xff0c;我大部分时间都在跟浏览器标签页打交道&#xff0c;直到第一次把桌面应用跑起来&#xff0c;才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词&#xff0c;最开始是在某段时间频繁出现在同事的讨论里&#xff0c;一个用HTML…

2026/11/18 13:59:04 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介&#xff1a;亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档&#xff0c;主要面向智能锁安装人员、终端用户及售后维护者&#xff0c;帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件&#xff0c;大小4.37MB&#xff0c;内容结构清晰&#xff…

2026/11/18 15:33:23 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统&#xff0c;整车要求空载跑到8m/s&#xff0c;电机转速已经拉到额定点&#xff0c;驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令&#xff0c;转速纹丝不动&#xff0c;三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/18 17:05:28 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年&#xff0c;用它写过嵌入式驱动、做过游戏服务端&#xff0c;也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词&#xff0c;我其实挺感慨的——这门语言的难点从来不是语法多&#xff0c;而是知识点之间的耦合太深…

2026/11/18 14:33:19 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介&#xff1a;亚太天能T109滑盖智能锁产品说明书以PDF格式发布&#xff0c;适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开&#xff0c;先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能&#xff0c;再给出完整安装步骤&…

2026/11/18 17:05:28 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历&#xff1a;翻开源码注释、论文摘要或者一份专业报告&#xff0c;每个字都认识&#xff0c;连在一起却像天书。想找人聊聊&#xff0c;身边要么没人懂&#xff0c;要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型&#xff0c;几秒钟之后&a…

2026/11/18 14:13:08 阅读更多 →

日新闻

周新闻

月新闻