【面试经典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 ,其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。 根据维基百科上 h 指数的定义:h 代表“高引用次数” ,一名科研人员的 h 指数 是指他(她&#x…...

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

每日一练 | 网络工程师软考真题Day31
阅读以下说明,答复以下【问题1】至【问题7】 【说明】 某网络拓扑结构如图3-1所示。网络A中的DNS_Server1和网络B中的DNS_Server2分别安装有Windows Server 2003并启用了DNS效劳。DNS_Server1中安装有IIS6.0,建立了一个域名为 abc 的Web站点。 图3-1 【…...
最优化:建模、算法与理论(优化建模——2)
3.10 K-均值聚类 聚类分析是 统计学中的一个基本问题,其在机器学习,数据挖掘,模式识别和图像分析中有着重要应用。聚类不同于分类,在聚类问题中我们仅仅知道数据点本身,而不知道每个数据点具体的标签。聚类分析的任务…...

库的相关操作
目录 一、创建数据库 1,创建数据库规则 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地址为: " <…...
Jtti:windows虚拟机如何设定永久静态路由
在Windows虚拟机上设置永久静态路由需要使用命令行工具,具体步骤如下: 打开命令提示符: 在Windows虚拟机中,按下Win R组合键,输入"cmd"并按回车键,以打开命令提示符。 查看当前路由表࿱…...
RocketMQ(3)之事务消息
一、发送事务消息案例 事务消息共有三种状态,提交状态、回滚状态、中间状态: TransactionStatus.CommitTransaction: 提交事务,它允许消费者消费此消息。TransactionStatus.RollbackTransaction: 回滚事务,它代表该消息将被删除…...

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

API接口与电商平台之间的联系,采集京东平台数据按关键字搜索商品接口示例
关键字搜索商品的重要性: 1.引入精准流量 关键词第一个也是最重要的作用就是为我们宝贝引进精准的流量,这一作用无论是在自然搜索中还是直通车中都是一样的。 第一步关乎的是我们宝贝的展现,而第二步用户是否会点进我们的宝贝,…...
代码随想录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,类型函数 isnumber(value) - 判断是否为数字isstring(value) - 判断是否为字符串isurl(value) - 判断是否为urliscolor(value) - 判断是否为颜色isunit(value, unit) - 判断value值是否为指定单位 示例: isnumber(12); // true isnumber(#333); // f…...

pdf转换成图片转换器在线怎么转?pdf转换成图片具体方法介绍
很多用户们都是比较喜欢使用pdf文档的,由于这种文件格式的便携性非常高,所以广泛的应用于工作和学习领域,再加上pdf文档可以随意转换成为其他的文件格式,更是让pdf文档受到了更多用户们的欢迎,那么pdf转换成图片转换器…...
JavaScript动态设置浏览器可视区域元素的文字颜色、监听滚动条、querySelectorAll、getBoundingClientRect
文章目录 前言htmlJavaScriptquerySelectorAllgetBoundingClientRect 前言 当元素出现在浏览器可视区域时给元素设置颜色等其他操作,比如当元素进入浏览器可视区域时,设置元素进入动画。 html <div id"idBox" class"box"><…...

意向客户的信息获取到底是怎样的,快来get一下
客户信息获取技术真的可以为企业提供精准客源吗?这个渠道到底安不安全,技术到底成不成熟?效果到底如何?下面简单的和大家分析一下。 客户信息获取技术是怎样的 手机采集引流方面,上量不精准,精准不上量的说…...
自动化测试常用脚本语言有哪些?
在自动化测试中,常用的脚本语言包括: 1. Python:Python是一个简洁、易读且功能强大的脚本语言,广泛应用于自动化测试领域。它具有丰富的测试框架和库,可以用于Web、移动应用和API等各种类型的测试。 2. Java࿱…...
mapreduce 的工作原理以及 hdfs 上传文件的流程
推荐两篇博文 mapreduce 的工作原理: 图文详解 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 - 倒计时组件-优化循环时间倒计时
使用定时器的规避方法 为了避免定时器误差导致倒计时计算错误,可以采用一些规避方法,比如将倒计时被中断时的剩余时间记录下来,重新开启定时器时再将这个剩余时间加到新的计算中。同时,为了避免定时器延迟,可以在每次执…...
java 实现访问者模式
访问者模式是一种行为设计模式,它允许您在不修改对象结构的情况下,向对象结构中的元素添加新的操作。这通常用于解决对象结构中元素类型多变,但操作类型相对稳定的问题。在访问者模式中,我们有一个访问者接口和多个具体的元素类&a…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具
作者:来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗?了解下一期 Elasticsearch Engineer 培训的时间吧! Elasticsearch 拥有众多新功能,助你为自己…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...

使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...

USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...
CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝
目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为:一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

给网站添加live2d看板娘
给网站添加live2d看板娘 参考文献: stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下,文章也主…...

恶补电源:1.电桥
一、元器件的选择 搜索并选择电桥,再multisim中选择FWB,就有各种型号的电桥: 电桥是用来干嘛的呢? 它是一个由四个二极管搭成的“桥梁”形状的电路,用来把交流电(AC)变成直流电(DC)。…...