力扣刷题---LCS 02. 完成一半题目【简单】

devtools/2024/9/23 6:28:44/

在这里插入图片描述


题目描述

有 N 位扣友参加了微软与力扣举办了「以扣会友」线下活动。主办方提供了 2*N 道题目,整型数组 questions 中每个数字对应了每道题目所涉及的知识点类型。 若每位扣友选择不同的一题,请返回被选的 N 道题目至少包含多少种知识点类型。

示例 1:

输入:questions = [2,1,6,2]

输出:1

解释:有 2 位扣友在 4 道题目中选择 2 题。 可选择完成知识点类型为 2 的题目时,此时仅一种知识点类型 因此至少包含 1 种知识点类型。

示例 2:

输入:questions = [1,5,1,3,4,5,2,5,3,3,8,6]

输出:2

解释:有 6 位扣友在 12 道题目中选择题目,需要选择 6 题。 选择完成知识点类型为 3、5 的题目,因此至少包含 2 种知识点类型。


算法分析

标签:哈希表,排序
1.先定义一个哈希表,用于统计每种数字出现的次数
2.将哈希表中的value值排序
3.根据次数与题目的数量进行比较,定义一个sum用于记录次数和,直到sum大于等于题目的数量

在这里插入图片描述

完整代码

class Solution {
public:int halfQuestions(vector<int>& questions) {int n=questions.size();int num=n/2;//题目数量unordered_map<int,int>m;    for(auto i:questions)    {m[i]++;//key为类型,统计数量    }vector<int>v;//把map当中的value放到数组中    for(auto x:m)    {v.push_back(x.second);    }//从大到小排序    sort(v.begin(),v.end(),greater<int>());    int count=0;//统计需要找多少个数字    int sum=0;//当前的和    for(int i=0;i<v.size();i++)    {sum+=v[i];    count++;    if(sum>=num)    break;//如果找到了,立即停止    }return count;    }
};

在这里插入图片描述


http://www.ppmy.cn/devtools/44385.html

相关文章

集成ECharts到若依框架:原理与使用方法详解

ECharts 是一个强大的开源数据可视化库&#xff0c;基于 JavaScript&#xff0c;能够创建丰富多彩的图表和交互数据展示。结合若依框架&#xff08;RuoYi&#xff09;&#xff0c;我们可以非常方便地将 ECharts 集成到系统中&#xff0c;实现数据的可视化展示。本文将详细介绍 …

系统架构设计师【第3章】: 信息系统基础知识 (核心总结)

文章目录 3.1 信息系统概述3.1.1 信息系统的定义3.1.2 信息系统的发展3.1.3 信息系统的分类3.1.4 信息系统的生命周期3.1.5 信息系统建设原则3.1.6 信息系统开发方法 3.2 业务处理系统&#xff08;TPS&#xff09;3.2.1 业务处理系统的概念3.2.2 业务处理系统的功能 …

【启程Golang之旅】运算符与流程控制讲解

欢迎来到Golang的世界&#xff01;在当今快节奏的软件开发领域&#xff0c;选择一种高效、简洁的编程语言至关重要。而在这方面&#xff0c;Golang&#xff08;又称Go&#xff09;无疑是一个备受瞩目的选择。在本文中&#xff0c;带领您探索Golang的世界&#xff0c;一步步地了…

安卓开发板_开发评估套件_4G/5G联发科MTK安卓主板定制开发

安卓开发板采用了联发科八核A53 CPU&#xff0c;主频2.0GHz&#xff0c;采用12nm制程工艺&#xff0c;拥有强大的通用计算性能。配备GE8300 GPU&#xff0c;支持1080P视频编码和H.264硬解码&#xff0c;能够解析目前流行的视频和图片格式&#xff0c;非常适合各种功能APP的测试…

Vuex 页面刷新数据丢失怎么解决

当Vuex中的数据在页面刷新后丢失时&#xff0c;这通常是因为Vuex的状态数据是保存在运行内存中的&#xff0c;页面刷新会导致Vue实例重新加载&#xff0c;进而Vuex中的数据被重置为初始状态。为了解决这个问题&#xff0c;可以采取以下几种方法&#xff1a; 1. 使用浏览器的本…

小短片创作-理论知识(三)

1、抗锯齿 1.相机移动的时候出现锯齿 2.当1个像素在三角形边缘的时候&#xff0c;可能取值为白色&#xff0c;也可能取值为黑色&#xff0c;表现出来就是闪烁&#xff0c;或锯齿 3.如果我们通过超采样将1个像素变成4个像素进行计算&#xff0c;得到的结果就会更准确&#x…

Docker安装nginx详细教程

详细教程如下&#xff1a; 1. 拉取Nginx镜像 docker pull nginx默认拉最新的&#xff08;也可以根据自己的需求指定版本&#xff09; 2. 运行Nginx容器 docker run --name my-nginx -d -p 80:80 nginx--name my-nginx&#xff1a;容器名称&#xff0c;便于管理。-d&#xf…

accelerate训练SD-LoRA,解决ValueError: Attempting to unscale FP16 gradients.问题

训练指令需从原来的&#xff1a; accelerate launch –mixed_precision“fp16” train_text_to_image_lora.py –pretrained_model_name_or_path“F:/XYX/Documents/AITools/ControlNetImplement/ControlNetTest/models–runwayml–stable-diffusion-v1-5” –dataset_name“d…