Leetcode.275 H 指数 II
题目链接
Leetcode.275 H 指数 II
mid
题目描述
给你一个整数数组 c i t a t i o n s citations citations ,其中 c i t a t i o n s [ i ] citations[i] citations[i] 表示研究者的第 i i i 篇论文被引用的次数, c i t a t i o n s citations citations 已经按照 升序排列 。计算并返回该研究者的 h h h 指数。
h h h 指数的定义: h h h 代表“高引用次数”( h i g h c i t a t i o n s high citations highcitations),一名科研人员的 h h h 指数是指他(她)的 ( n n n 篇论文中)总共有 h h h 篇论文分别被引用了至少 h h h 次。
请你设计并实现对数时间复杂度的算法解决此问题。
示例 1:
输入:citations = [0,1,3,5,6]
输出:3
解释:给定数组表示研究者总共有 5 篇论文,每篇论文相应的被引用了 0, 1, 3, 5, 6 次。
由于研究者有3篇论文每篇 至少 被引用了 3 次,其余两篇论文每篇被引用 不多于 3 次,所以她的 h 指数是 3 。
示例 2:
输入:citations = [1,2,100]
输出:2
提示:
- n = c i t a t i o n s . l e n g t h n = citations.length n=citations.length
- 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1≤n≤105
- 0 ≤ c i t a t i o n s [ i ] ≤ 1000 0 \leq citations[i] \leq 1000 0≤citations[i]≤1000
- c i t a t i o n s citations citations 按 升序排列
解法:二分
初始 l = 0 , r = n l = 0 , r = n l=0,r=n;
我们可以得到 m i d mid mid ,如果 c i t a t i o n s citations citations 中 大于等于 m i d mid mid 的元素一共有 c n t cnt cnt 个。
- 如果 c n t ≥ m i d cnt \geq mid cnt≥mid,说明 c n t cnt cnt 指数,是满足 c i t a t i o n s citations citations 的,故 l = m i d l = mid l=mid;
- 如果 c n t ≥ m i d cnt \geq mid cnt≥mid,说明 c n t cnt cnt 指数,不满足 c i t a t i o n s citations citations 的,故 r = m i d − 1 r = mid - 1 r=mid−1;
时间复杂度: O ( l o g 2 n ) O(log^2n) O(log2n)
C++代码:
class Solution {
public:int hIndex(vector<int>& citations) {int n = citations.size();int l = 0  , r = n;while(l < r){int mid = (l + r + 1) >> 1;auto it = lower_bound(citations.begin(),citations.end(),mid);int cnt = citations.end() - it;if(cnt >= mid) l = mid;else r = mid - 1;}return l;}
};
相关文章:
Leetcode.275 H 指数 II
题目链接 Leetcode.275 H 指数 II mid 题目描述 给你一个整数数组 c i t a t i o n s citations citations ,其中 c i t a t i o n s [ i ] citations[i] citations[i] 表示研究者的第 i i i 篇论文被引用的次数, c i t a t i o n s citations citat…...
代码随想录Day40-单调栈:力扣第496e、503m、42h、84h题
496e. 下一个更大元素 I 题目链接 代码随想录文章讲解链接 方法一:单调栈哈希表 用时:13m52s 思路 维护一个栈底到栈顶是单调递减的栈,从后往前遍历数组nums2,更新栈。nums2当前元素nums2[i]的下一个更大元素就是栈顶元素&am…...
 
Git窗口打开vim后如何退出编辑(IDEA/Goland等编辑器)
最近在学习git高级操作过程中,遇到了一下问题: 我在学习Git合并多个commit为一个的时候,需要输入一个命令 git rebase -i HEAD~2 这说明已经是编辑模式了。当我写好后,我还按照原来在linux上的按下ESC键,但是只是光…...
【CSDN 每日一练 ★★☆】【二叉树/BSF】二叉树的层序遍历
【CSDN 每日一练 ★★☆】【二叉树/BSF】二叉树的层序遍历 二叉树 BSF 题目 给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。 示例: 二叉树:[3,9,20,null,nul…...
 
Golang | Zinx学习笔记(一)
参考 http://zinx.me/ https://www.kancloud.cn/aceld/zinx/1960213 https://www.yuque.com/aceld/tsgooa/gx01meg5ow4pftac 说明 zinx是一个基于Golang的轻量级并发服务器框架。 目前zinx已经在很多企业进行开发使用,具体使用领域包括:后端模块的消息中转、长链…...
 
【Java 进阶篇】在Java Web应用中获取ServletContext对象详解
在Java Web应用开发中,ServletContext对象扮演着重要的角色,它允许你在整个Web应用程序中存储和共享数据。ServletContext对象是Servlet容器提供的一种用于管理Web应用程序的全局信息的方式。本文将详细探讨ServletContext对象的概念、用途以及如何在Jav…...
 
负债6W,依靠这个项目副业6个月还清欠款,还多存了10W+
真不敢想象负债6W“走投无路”的我还能通过副业逆天翻盘,6个月还清欠款,还让我多了10W存款,现在小日子也是相当滋润,吃穿不愁,不用过多为生计而奔波操劳。 仅代表个人收益 网盘下载地址:【安卓软件】音魔变…...
 
快速了解ClickHouse!
简介 ClickHouse是一个开源列式数据库管理系统(DBMS),用于在线分析处理(OLAP): 列式存储:与传统的行式数据库不同,ClickHouse以列的形式存储数据,这使得在分析大量数据时…...
 
PythonWEB
文章目录 前端简介1. 什么是网页2. 网页的组成3. 网页的优势4. 前端三剑客5. 编写步骤6. HTTP协议 HTML51. HTML介绍2. 元素3. 使用4. 基本结构解析5. 常用标签文本标签容器标签列表标签表格标签表单标签 对于文件数据的提交需要满足以下两个条件:6. 标签分类 前端简…...
 
【工具问题】IDEA每次关闭的时候都会弹框显示closing project,然后弹框持续很久就像卡住了
idea关闭的时候出现问题 问题展示为什么会出现这种情况怎么解决 问题展示 我idea已经关闭了,但是这个弹框要持续很久才能关闭 为什么会出现这种情况 我的plugins原本是加载不出来的,所以我按照网上说法去做 怎么解决 file->setting,再如图选择…...
 
从瀑布模式到水母模式:ChatGPT如何赋能软件研发全流程
文章目录 前言内容简介作者简介专家推荐读者对象直播预告 前言 计算机技术的发展和互联网的普及,使信息处理和传输变得更加高效,极大地改变了金融、商业、教育、娱乐等领域的运作方式。数据分析、人工智能和云计算等新兴技术,也在不断地影响和…...
 
类变量/方法、main语法、代码块
一.类变量和方法 思维导图概览: 1.1类变量(静态变量) 1.什么叫做类变量/方法? ——给类中的成员属性或成员方法加上static关键字进行修饰,类变量/方法也叫做静态变量/方法,静态变量/方法被类的自身所有对…...
[SHCTF 校外赛道] crypto
终于都结束了,这些新生赛太漫长了。不过这个也还是有些难度的,好多整不来。抓紧时间整理一下。 week1 第1周基本是古典密码,古典和现代最大的区别是古典全靠猜,现在都是数学 立正 wl hgrfhg 4gNUx4NgQgEUb4NC64NHxZLg636V6CDBi…...
 
vue3从基础到入门(一)
文章目录 简介提升使用创建脚手架vite 常用Composition APIsetuprefreactive函数响应式vue2响应式vue3实现响应式 reactive对比ref注意计算属性computed函数 监视watch函数watchEffect函数 生命周期hook函数toRef 简介 2020年9月18日,Vue.js发布3.0版本,…...
枚举类型 表示不同的 HTTP 状态码和相应的错误消息
java web业务中经常用常量来表示不同的 HTTP 响应状态,比如 public enum AppHttpCodeEnum {// 成功段0SUCCESS(200,"操作成功"),// 登录段1~50NEED_LOGIN(1,"需要登录后操作"),LOGIN_PASSWORD_ERROR(2,"密码错误"),// TOKEN50~100TOKEN_INVALID…...
 
SAP 使用cl_gui_timer自动刷新屏幕的用法详解 <转载>
原文链接:https://blog.csdn.net/SAPmatinal/article/details/130483382 SAP 使用cl_gui_timer自动刷新屏幕的用法详解 这个类在初始化的时候会设置一个定时间隔,每隔这个时间就会触发一次FINISHED事件。利用这个类的特性,可以实现很多东西&…...
 
golang中的Interface接口 类型断言、接口赋值、空接口的使用、接口嵌套
Interface整理 文章目录 Interface整理接口嵌套接口类型断言类型判断 type-switch使用方法集与接口空接口实例 接口赋值给接口 接口是一种契约,实现类型必须满足它,它描述了类型的行为,规定类型可以做什么。接口彻底将类型能做什么࿰…...
使用设计模式省去大量的if-elsef分支
1.测试类 Testpublic void test7() {/*** 使用设计模式前*///模拟入参String name "?";if("张三".equals(name)){System.out.println("按照张三的策略执行的任务!");}else if ("李四".equals(name)){System.out.println("按照李…...
 
Tomcat安装与配置文件解读
简介 Tomcat是Apache软件基金会(Apache Software Foundation)项目中的一个核心项目,由Apache、Sun和其他一些公司及个人共同开发而成。 Tomcat服务器是一个免费的开放源代码的Web应用服务器,属于轻量级应用服务器,在…...
 
计算机网络重点概念整理-第一章 计算机网络概述【期末复习|考研复习】
计算机网络复习系列文章传送门: 第一章 计算机网络概述 第二章 物理层 第三章 数据链路层 第四章 网络层 第五章 传输层 第六章 应用层 第七章 网络安全 计算机网络整理-简称&缩写 文章目录 前言一、计算机网络概述1.1 计算机网络的定义:1.2 计算机网…...
 
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
 
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果 
Reasoning over Uncertain Text by Generative Large Language Models
https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...
 
HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
 
Linux 内存管理实战精讲:核心原理与面试常考点全解析
Linux 内存管理实战精讲:核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用,还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...
 
C++ 设计模式 《小明的奶茶加料风波》
👨🎓 模式名称:装饰器模式(Decorator Pattern) 👦 小明最近上线了校园奶茶配送功能,业务火爆,大家都在加料: 有的同学要加波霸 🟤,有的要加椰果…...
MySQL 主从同步异常处理
阅读原文:https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主,遇到的这个错误: Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一,通常表示ÿ…...
 
解析两阶段提交与三阶段提交的核心差异及MySQL实现方案
引言 在分布式系统的事务处理中,如何保障跨节点数据操作的一致性始终是核心挑战。经典的两阶段提交协议(2PC)通过准备阶段与提交阶段的协调机制,以同步决策模式确保事务原子性。其改进版本三阶段提交协议(3PC…...
 
【51单片机】4. 模块化编程与LCD1602Debug
1. 什么是模块化编程 传统编程会将所有函数放在main.c中,如果使用的模块多,一个文件内会有很多代码,不利于组织和管理 模块化编程则是将各个模块的代码放在不同的.c文件里,在.h文件里提供外部可调用函数声明,其他.c文…...
