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

【面试经典150题】H 指数

题目链接

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

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

  • n == citations.length
  • 1 <= n <= 5000
  • 0 <= citations[i] <= 1000

关键就是这句“至少发表了 h 篇论文,并且每篇论文 至少 被引用 h 次”,简单点说就是找出 h 个元素,里面每个值都大于等于 h。

方法1:

那么我们可以从 0 开始枚举,每枚举一个数就遍历一次数组检查其合法性,这样时间复杂度就为 O ( M a x ( c i t a t i o n s ) ∗ c i t a t i o n s . l e n g t h ) O(Max(citations) * citations.length) O(Max(citations)citations.length),最多执行 5*10^6 次。

/*** @param {number[]} citations* @return {number}*/var hIndex = function (citations) {let k = 0;let candidate=0;while (k <= citations.length) {let count = 0;for (let i = 0; i < citations.length; i++) {citations[i] >= k && count++;if (count >= k && k !== 0) {candidate = k;break;}}k++;}return candidate;
};

在 leetcode 上的运行时间击败率太低。

我们另寻他路。

方法2:

将数组进行从大到小的排序,往后遍历,自增量 i 加上 1 就是当前发表论文的最大数量,而当前值 citations[i] 就是其中的最小值,只要满足 citations[i]>=i+1就是我们要寻找的最大的 H 指数。

/*** @param {number[]} citations* @return {number}*/var hIndex = function (citations) {citations.sort((a, b) => b - a);let h = 0;for (let i = 0; i < citations.length; i++){if (citations[i] >= i + 1) {h = i+1;} else {return h;}}return h;
};

sort 排序的算法是该方法的时间复杂度的主要开销,其底层实现做了很多优化。

V8引擎中数组的sort源码

源码注释说:This file implements a stable, adapative merge sort variant called TimSort.

意思是说它是一个稳定的自适应归并排序,称为 TimSort。

相关文章:

【面试经典150题】H 指数

题目链接 给你一个整数数组 citations &#xff0c;其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。 根据维基百科上 h 指数的定义&#xff1a;h 代表“高引用次数” &#xff0c;一名科研人员的 h 指数 是指他&#xff08;她&#x…...

ARM DIY(十)LRADC 按键

前言 ARM SOC 有别于单片机 MCU 的一点就是&#xff0c;ARM SOC 的 GPIO 比较少&#xff0c;基本上引脚都有专用的功能&#xff0c;因为它很少去接矩阵键盘、众多继电器、众多 LED。 但有时 ARM SOC 又需要三五个按键&#xff0c;这时候 LRADC 就是一个不错的选择&#xff0c;…...

每日一练 | 网络工程师软考真题Day31

阅读以下说明&#xff0c;答复以下【问题1】至【问题7】 【说明】 某网络拓扑结构如图3-1所示。网络A中的DNS_Server1和网络B中的DNS_Server2分别安装有Windows Server 2003并启用了DNS效劳。DNS_Server1中安装有IIS6.0&#xff0c;建立了一个域名为 abc 的Web站点。 图3-1 【…...

最优化:建模、算法与理论(优化建模——2)

3.10 K-均值聚类 聚类分析是 统计学中的一个基本问题&#xff0c;其在机器学习&#xff0c;数据挖掘&#xff0c;模式识别和图像分析中有着重要应用。聚类不同于分类&#xff0c;在聚类问题中我们仅仅知道数据点本身&#xff0c;而不知道每个数据点具体的标签。聚类分析的任务…...

库的相关操作

目录 一、创建数据库 1&#xff0c;创建数据库规则 2、创建案例 二、字符集和校验规则 1、查看系统默认字符集以及校验规则 2、查看数据库支持的字符集以及校验规则 3、校验规则对数据库的影响 三、操纵数据库 1、查看数据库和目前所在数据库 2、显示创建语句 3、修改数据库 4、…...

程序分区:全局区、常量区、栈区、堆区、代码区

#include <iostream> using namespace std; //全局变量 int g_a 10; int g_b 10; //全局常量 const int c_g_a 10; const int c_g_b 10;int main() { //局部变量 int a 10; int b 10; //打印地址 cout << "局部变量a地址为&#xff1a; " <…...

Jtti:windows虚拟机如何设定永久静态路由

在Windows虚拟机上设置永久静态路由需要使用命令行工具&#xff0c;具体步骤如下&#xff1a; 打开命令提示符&#xff1a; 在Windows虚拟机中&#xff0c;按下Win R组合键&#xff0c;输入"cmd"并按回车键&#xff0c;以打开命令提示符。 查看当前路由表&#xff1…...

RocketMQ(3)之事务消息

一、发送事务消息案例 事务消息共有三种状态&#xff0c;提交状态、回滚状态、中间状态&#xff1a; TransactionStatus.CommitTransaction: 提交事务&#xff0c;它允许消费者消费此消息。TransactionStatus.RollbackTransaction: 回滚事务&#xff0c;它代表该消息将被删除…...

基于多设计模式下的同步异步日志系统

基于多设计模式下的同步&异步日志系统 代码链接&#xff1a;https://github.com/Janonez/Log_System 1. 项目介绍 本项目主要实现一个日志系统&#xff0c; 其主要支持以下功能&#xff1a; 支持多级别日志消息支持同步日志和异步日志支持可靠写入日志到标准输出、文件…...

API接口与电商平台之间的联系,采集京东平台数据按关键字搜索商品接口示例

关键字搜索商品的重要性&#xff1a; 1.引入精准流量 关键词第一个也是最重要的作用就是为我们宝贝引进精准的流量&#xff0c;这一作用无论是在自然搜索中还是直通车中都是一样的。 第一步关乎的是我们宝贝的展现&#xff0c;而第二步用户是否会点进我们的宝贝&#xff0c;…...

代码随想录day41|343. 整数拆分96. 不同的二叉搜索树

343. 整数拆分 class Solution:def integerBreak(self, n: int) -> int:dp [0] *(n1)dp[2]1if n <3:return dp[n]for i in range(3,n1):for j in range(1,n):dp[i]max(j*(i-j),j*dp[i-j],dp[i])return dp[n] 96. 不同的二叉搜索树 class Solution:def numTrees(self, …...

Less常用内置函数

1&#xff0c;类型函数 isnumber(value) - 判断是否为数字isstring(value) - 判断是否为字符串isurl(value) - 判断是否为urliscolor(value) - 判断是否为颜色isunit(value, unit) - 判断value值是否为指定单位 示例&#xff1a; isnumber(12); // true isnumber(#333); // f…...

pdf转换成图片转换器在线怎么转?pdf转换成图片具体方法介绍

很多用户们都是比较喜欢使用pdf文档的&#xff0c;由于这种文件格式的便携性非常高&#xff0c;所以广泛的应用于工作和学习领域&#xff0c;再加上pdf文档可以随意转换成为其他的文件格式&#xff0c;更是让pdf文档受到了更多用户们的欢迎&#xff0c;那么pdf转换成图片转换器…...

JavaScript动态设置浏览器可视区域元素的文字颜色、监听滚动条、querySelectorAll、getBoundingClientRect

文章目录 前言htmlJavaScriptquerySelectorAllgetBoundingClientRect 前言 当元素出现在浏览器可视区域时给元素设置颜色等其他操作&#xff0c;比如当元素进入浏览器可视区域时&#xff0c;设置元素进入动画。 html <div id"idBox" class"box"><…...

意向客户的信息获取到底是怎样的,快来get一下

客户信息获取技术真的可以为企业提供精准客源吗&#xff1f;这个渠道到底安不安全&#xff0c;技术到底成不成熟&#xff1f;效果到底如何&#xff1f;下面简单的和大家分析一下。 客户信息获取技术是怎样的 手机采集引流方面&#xff0c;上量不精准&#xff0c;精准不上量的说…...

自动化测试常用脚本语言有哪些?

在自动化测试中&#xff0c;常用的脚本语言包括&#xff1a; 1. Python&#xff1a;Python是一个简洁、易读且功能强大的脚本语言&#xff0c;广泛应用于自动化测试领域。它具有丰富的测试框架和库&#xff0c;可以用于Web、移动应用和API等各种类型的测试。 2. Java&#xff1…...

mapreduce 的工作原理以及 hdfs 上传文件的流程

推荐两篇博文 mapreduce 的工作原理&#xff1a; 图文详解 MapReduce 工作流程_mapreduce工作流程_Shockang的博客-CSDN博客 hdfs 上传文件的流程 HDFS原理 - 知乎...

Ubuntu22.04安装ROS2

Ubuntu22.04安装ROS2 Excerpt ROS2官方文档 ROS2清华镜像站sudo apt update sudo apt upgrade locale # check for UTF-8 sudo apt update && sudo apt install locales sudo locale-gen en_US en_US.UTF-8 sudo update-locale LC_ALLe… ROS2官方文档 ROS2清华镜像站…...

uniapp - 倒计时组件-优化循环时间倒计时

使用定时器的规避方法 为了避免定时器误差导致倒计时计算错误&#xff0c;可以采用一些规避方法&#xff0c;比如将倒计时被中断时的剩余时间记录下来&#xff0c;重新开启定时器时再将这个剩余时间加到新的计算中。同时&#xff0c;为了避免定时器延迟&#xff0c;可以在每次执…...

java 实现访问者模式

访问者模式是一种行为设计模式&#xff0c;它允许您在不修改对象结构的情况下&#xff0c;向对象结构中的元素添加新的操作。这通常用于解决对象结构中元素类型多变&#xff0c;但操作类型相对稳定的问题。在访问者模式中&#xff0c;我们有一个访问者接口和多个具体的元素类&a…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...