当前位置: 首页 > news >正文

LeetCode面试150——274H指数

题目难度:中等

默认优化目标:最小化平均时间复杂度。

Python默认为Python3。

目录

1 题目描述

2 题目解析

3 算法原理及代码实现

3.1 排序

3.2 排序时间优化(计数排序)

3.3 二分查找

参考文献


1 题目描述

给你一个整数数组 citations ,其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数

根据维基百科上 h 指数的定义:h 代表“高引用次数” ,一名科研人员的 h 指数 是指他(她)至少发表了 h 篇论文,并且 至少h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值,h 指数 是其中最大的那个。

示例 1:

输入:citations = [3,0,6,1,5]
输出:3 
解释:给定数组表示研究者总共有 5 篇论文,每篇论文相应的被引用了 3, 0, 6, 1, 5 次。由于研究者有 3 篇论文每篇 至少 被引用了 3 次,其余两篇论文每篇被引用 不多于 3 次,所以她的 h 指数是 3。

示例 2:

输入:citations = [1,3,1]
输出:1

提示:

  • n == citations.length

  • 1 <= n <= 5000

  • 0 <= citations[i] <= 1000

2 题目解析

输入是数组citations(引用的英文),输出是h指数。citations的长度n代表总共发表的论文篇数,下标代表论文名,元素值代表论文被引用的次数。

h指数的意思为,citations中有h篇论文被引用次数超过了h次。如示例2中,h取1,至少发表了一篇论文引用次数超过1,h指数为1。h取2,至少发表了2篇论文引用次数超过2,不成立。h取3,至少发表了3篇论文引用次数超过3,不成立。

暴力求法是先计算citations长度n,然后每个元素去和n比大小,都大于则输出n,否则接着和n=n-1比大小,以此类推。平均时间复杂度为O(n!)。

3 算法原理及代码实现

3.1 排序

在暴力求法的基础上,我们先对citations排序,变成一个有序数组。假如是升序排序,一次循环从后向前遍历。

题目中至少就是大于的意思,比如至少大于 1次就是>0,至少大于h次就是>h。因此初始化h=0。citations[i]和h比大小,如果citations[i]大于h,h++,反之不执行任何操作。最后输出h即可。

平均时间复杂度为O(n log n)(采用快排),平均空间复杂度为O(1)。

C++代码实现

class Solution {
public:int hIndex(vector<int>& citations) {int n=citations.size();int h=0;
​sort(citations.begin(),citations.end());
​for(int i=n-1;i>=0;i--){if(citations[i]>h){h++;}}
​return h;
​}
};

Python代码实现

class Solution:def hIndex(self, citations: List[int]) -> int:citations.sort()h = 0n = len(citations)for i in range(n-1, -1, -1):if citations[i] > h:h += 1return h
 

3.2 排序时间优化(计数排序)

从3.1可以看到,平均时间复杂度和排序算法的时间复杂度相同。我们可以牺牲空间换时间,使用计数排序进一步降低时间复杂度。

新建一个计数数组counter,将citations中论文引用次数映射到counter中。映射规则如下:如果元素值大于n,counter[n]++;反之,对应引用次数的下标位置citations[i],计数数组counter[citations[i]]++

平均时间复杂度为O(n),平均空间复杂度为O(n)。

C++代码实现如下

class Solution {
public:int hIndex(vector<int>& citations) {int n=citations.size();vector<int> counter(n+1);int h=0;
​//计数排序for(int i=0;i<n;i++){if(citations[i]>n){counter[n]++;}else{counter[citations[i]]++;}}
​for(int i=n;i>=0;i--){h+=counter[i];//引用至少h次的论文总数if(h>=i){//这里的i代表引用次数return i;}}
​return 0;
​}
};

Python代码实现

class Solution:def hIndex(self, citations: List[int]) -> int:n = len(citations)counter = [0] * (n + 1)h = 0
​# 计数排序for citation in citations:if citation > n:counter[n] += 1else:counter[citation] += 1
​for i in range(n, -1, -1):h += counter[i]  # 引用至少 h 次的论文总数if h >= i:  # 这里的 i 代表引用次数return i
​return 0

3.3 二分查找

设左边界为left,右边界为right,中点为mid。我们可以把原问题拆分成若干个子问题:判断至少有mid数大于mid。如果在区间[mid,right]满足,说明搜寻的h在右边,反之在左边。

平均时间复杂度O(n log n),平均空间复杂度O(1)

class Solution {
public:int hIndex(vector<int>& citations) {return binarySearch(citations, 0, citations.size());}
​
private:int binarySearch(vector<int>& citations, int left, int right) {if (left >= right) {return left;}
​int mid = (left + right + 1) >> 1;int cnt = 0;for (int i = 0; i < citations.size(); i++) {if (citations[i] >= mid) {cnt++;}}
​if (cnt >= mid) {return binarySearch(citations, mid, right);} else {return binarySearch(citations, left, mid - 1);}}
};
​

Python代码实现

class Solution:def hIndex(self, citations: List[int]) -> int:return self.binarySearch(citations, 0, len(citations))
​def binarySearch(self, citations, left, right):if left >= right:return left
​mid = (left + right + 1) // 2cnt = sum(1 for citation in citations if citation >= mid)
​if cnt >= mid:return self.binarySearch(citations, mid, right)else:return self.binarySearch(citations, left, mid - 1)
​

参考文献

力扣面试经典150题

力扣官方题解

相关文章:

LeetCode面试150——274H指数

题目难度&#xff1a;中等 默认优化目标&#xff1a;最小化平均时间复杂度。 Python默认为Python3。 目录 1 题目描述 2 题目解析 3 算法原理及代码实现 3.1 排序 3.2 排序时间优化(计数排序) 3.3 二分查找 参考文献 1 题目描述 给你一个整数数组 citations &#xf…...

【Linux】Linux重定向指南:探索输出重定向与追加重定向的奥秘!

欢迎来到 CILMY23 的博客 &#x1f3c6;本篇主题为&#xff1a;Linux重定向指南&#xff1a;探索输出重定向与追加重定向的奥秘&#xff01; &#x1f3c6;个人主页&#xff1a;CILMY23-CSDN博客 &#x1f3c6;系列专栏&#xff1a;Python | C | C语言 | 数据结构与算法 | 贪…...

Spring AI -快速开发ChatGPT应用

Spring AI介绍 Spring AI是AI工程师的一个应用框架&#xff0c;它提供了一个友好的API和开发AI应用的抽象&#xff0c;旨在简化AI应用的开发工序&#xff0c;例如开发一款基于ChatGPT的对话、图片、音频等应用程序。 Spring AI已经集成了OpenAI的API&#xff0c;因此我们不需…...

Modern C++ 智能指针

Why&#xff1f; 原始指针存在缺陷&#xff0c;不符合现代编程语言的需要。 原始指针的缺陷&#xff1a; 指针指向一片内存&#xff0c;使用者无法得知到底是指向了什么&#xff0c;是数组还是对象&#xff1f;使用完指针是否需要销毁&#xff1f;什么时候销毁&#xff1f;如…...

Python的100道经典练习题,每日一练,必成大神!!!

Python的100道经典练习题是一个广泛而深入的学习资源&#xff0c;可以帮助Python初学者和进阶者巩固和提升编程技能 完整的100多道练习题可在下面图片免沸获取哦~ 整理了100道Python的题目&#xff0c;如果你是一位初学者&#xff0c;这一百多道题可以 帮助你轻松的使用Python…...

代码回滚命令

定位到当前分支 git branch回滚到指定的commit git reset --hard 85da0cb8322accad143cpush到远程分支 git push --force...

[ASIS 2019]Unicorn shop1

打开题目 随便输入信息看一下 操作失败&#xff0c;只让输入一个字符 不妨抓包看一下&#xff0c;信息&#xff0c;发现 从中可以发现源代码是如何处理price的 使用的是unicodedata.numeric() 但我们查看页面源码时&#xff0c;看到源码处理方式是utf-8 所以&#xff0c;前…...

LangChain与泛型编程:探索代码生成的新维度

LangChain与泛型编程&#xff1a;探索代码生成的新维度 在软件开发领域&#xff0c;泛型编程是一种允许创建可重用组件的技术&#xff0c;这些组件可以在多种数据类型上工作的编程范式。LangChain作为一个假设的编程辅助工具&#xff0c;如果存在&#xff0c;它可能会支持泛型…...

day25

一、进程间通信&#xff08;IPC&#xff09; 1.1 进程间通信的引入 1> 对于多个线程之间通信&#xff0c;我们可以使用临界资源来完成&#xff0c;通过一个线程任务对临界资源进行修改&#xff0c;另一个线程也可以使用已经修改过的临界资源&#xff0c;但是要注意使用…...

红黑树的概念和模拟实现[C++]

文章目录 红黑树的概念一、红黑树的性质红黑树原理二、红黑树的优势和比较 红黑树的模拟实现构建红黑树的数据结构定义节点的基本结构和初始化方式插入新节点插入新节点的颜色调整颜色和结构以满足红黑树性质 红黑树的应用场景 红黑树的概念 一、红黑树的性质 红黑树是一种自平…...

网络安全应急响应概述

前言 在网络安全领域&#xff0c;有一句广为人知的话&#xff1a;“没有绝对的安全”。这意味着任何系统都有可能被攻破。安全攻击的发生并不可怕&#xff0c;可怕的是从头到尾都毫无察觉。当系统遭遇攻击时&#xff0c;企业的安全人员需要立即进行应急响应&#xff0c;以将影响…...

【C++】链表操作技巧综合:重排链表(带你理顺链表的做题思路)

1.题目 2.算法思路 这是一道关于链表的综合题&#xff0c;一共涉及到三个步骤&#xff0c;其中每个步骤单拎出来就可以当一道单独的题目。所以需要大家对链表的操作十分熟悉&#xff0c;否则可能需要大量的时间做这道题目&#xff0c;而且还要很多的bug。 第一个步骤&#xf…...

行为型设计模式2:观察者/职责链/中介者/访问者

设计模式&#xff1a;观察者/职责链/中介者/访问者 (qq.com)...

叛逆,批判

1、对以往说法的批判之一&#xff08;第一次这么公开批判是2004-2005年&#xff09;&#xff1a; 这部英文版的《数学百科全书》似乎是从俄语版翻译过来的&#xff1f;我查了三本引用的图书文献&#xff0c;都没有关于“nonsingular”和“singular”的类似下面的说法&#xff…...

Linux 命令,mkdir说明与使用

1&#xff1a;mkdir命令功用&#xff1a; 用于创建一个或多个目录&#xff0c;创建目录&#xff0c;必须在父目录中写上权限。 新目录的默认模式为0777&#xff0c;可以由系统或用的umask来修改。 2&#xff1a;命令构件: mkdir [options] directories 3:参数选项: -m&#x…...

24. 两两交换链表中的节点(Java)

目录 题目描述&#xff1a;示例 &#xff1a;代码实现&#xff1a; 题目描述&#xff1a; 给你一个链表&#xff0c;两两交换其中相邻的节点&#xff0c;并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题&#xff08;即&#xff0c;只能进行节点交换&am…...

linux虚拟机设置固定ip

修改/etc/sysconfig/network-scripts目录下ifcfg-eth0文件&#xff0c;各虚拟机这个文件名不一致&#xff0c;ifcfg-XX格式 vim /etc/sysconfig/network-scripts/ifcfg-eth0BOOTPROTO设置为static&#xff0c;然后在最后添加固定IP地址和默认网关、DNS等配置&#xff0c;IP地址…...

mysql问题解决

1.etl数据同步时&#xff0c;发现连接不上要同步的数据库 解决方法&#xff1a;关闭mysql的ssl&#xff0c;步骤如下&#xff1a; 在MySQL中禁用SSL连接涉及修改服务器的配置文件&#xff08;通常是my.cnf或my.ini&#xff0c;取决于你的操作系统和MySQL版本&#xff09;。以…...

类和对象(下)C++

1.初始化列表 1.为什么有初始化列表&#xff0c;它的作用&#xff1f; ->初始化列表&#xff0c;是构造函数初始化的另一种形式。 ->在语法上面理解&#xff0c;初始化列表可以认定为是每个成员变量定义初始化的地方. ->引用成员变量&#xff0c;const成员变量&am…...

常用在线 Webshell 查杀工具推荐

一、简介 这篇文章将介绍几款常用的在线 Webshell 查杀工具&#xff0c;包括长亭牧云、微步在线云沙箱、河马和VirusTotal。每个工具都有其独特的特点和优势&#xff0c;用于帮助用户有效检测和清除各类恶意 Webshell&#xff0c;保障网站和服务器的安全。文章将深入探讨它们的…...

SITS2026踩坑实录:47个生产环境AI推理延迟突增案例,含GPU调度错配、时序特征漂移检测及央行《智能风控接口规范》映射表

第一章&#xff1a;SITS2026案例&#xff1a;AI原生金融系统改造 2026奇点智能技术大会(https://ml-summit.org) 在2026年全球金融基础设施升级浪潮中&#xff0c;新加坡国际交易结算系统&#xff08;SITS&#xff09;启动代号为“Project Aether”的AI原生重构工程。该项目摒…...

手搓单片机

“手搓单片机”在电子爱好者的语境里&#xff0c;通常指绕开现成的开发板&#xff0c;自己从零搭建一个“最小系统”。这就像给芯片造一个能呼吸、能思考的“身体”。对于新手&#xff0c;最经典的入门路径是51单片机&#xff08;如 STC89C52&#xff09;。下面这份手搓指南分为…...

会议室音响 / 会议系统怎么选?2026 高口碑品牌盘点

在政企办公、学校报告厅、大型会议中心、指挥调度中心等场景&#xff0c;一套稳定、清晰、低啸叫、售后靠谱的会议系统&#xff0c;直接决定会议效率与专业形象。面对市面上五花八门的品牌与方案&#xff0c;很多人只看价格不看实力&#xff0c;最终出现啸叫、杂音、后排听不清…...

SQL如何利用JOIN优化查询复杂的多维度指标_预索引关联键

WHERE条件放错位置会导致预索引失效&#xff0c;因优化器被迫全量JOIN后再过滤&#xff1b;应将关联表筛选条件移至ON子句或建立(status,id)复合索引&#xff0c;并用EXPLAIN验证索引使用。JOIN 时为什么 WHERE 条件放错位置会让预索引失效MySQL 或 PostgreSQL 中&#xff0c;J…...

FFmpeg 与 C++ 实战音视频处理:从环境搭建到流媒体解析

1. 为什么选择FFmpeg与C组合 音视频处理就像在数字厨房里烹饪一道复杂的菜肴&#xff0c;你需要得心应手的厨具和精准的烹饪技巧。FFmpeg就是这个厨房里的瑞士军刀&#xff0c;而C则是那位能够精准控制火候的大厨。这套组合在业内被称为"音视频处理的黄金搭档"&#…...

深入解析C99中函数隐式声明无效警告的根源与解决方案

1. 为什么C99标准对函数隐式声明如此严格&#xff1f; 我第一次在嵌入式项目里遇到这个警告时&#xff0c;整个人都是懵的。当时正在调试STM32的定时器初始化代码&#xff0c;编译时突然蹦出"Warning: implicit declaration of function TIM2_Int_Init is invalid in C99&…...

OPTIGA™ Trust M安全芯片Arduino开发全解析

1. OPTIGA™ Trust M 安全芯片 Arduino 库深度解析Infineon OPTIGA™ Trust M 是一款面向物联网边缘设备的高安全性硬件安全模块&#xff08;HSM&#xff09;&#xff0c;其核心价值在于将密码学能力从软件层下沉至专用安全微控制器&#xff0c;从根本上规避密钥在主MCU内存中明…...

Windows/Mac双平台实测:Caption滚动字幕软件如何5分钟打造高逼格桌面特效

Windows/Mac双平台实测&#xff1a;Caption滚动字幕软件如何5分钟打造高逼格桌面特效 在数字内容创作领域&#xff0c;视觉冲击力往往决定着作品的传播效果。无论是自媒体博主的视频包装&#xff0c;还是创意工作者的项目展示&#xff0c;动态文字元素总能成为吸引眼球的利器。…...

AI原生研发供应商怎么选?2024最新Gartner交叉验证的5大否决项与3个隐形红线

第一章&#xff1a;AI原生软件研发供应商评估标准的范式迁移 2026奇点智能技术大会(https://ml-summit.org) 传统软件供应商评估体系聚焦于项目交付周期、人力成本与文档完备性&#xff0c;而AI原生软件的研发本质已发生根本性转变&#xff1a;模型即服务&#xff08;MaaS&am…...

如果大家都不断进步,模型最终是不是都差不多?

并不是。整体实力可能趋于一致&#xff0c;但模型或仍将保留差异化优势&#xff0c;市场不太可能最终形成赢家通 吃的格局。 的确&#xff0c;所有主要公司都在努力提高模型质量&#xff0c;但这并不意味着它们可以互相替代。不同公司在架构、训练数据、产品侧重点及技术方向上…...