【面试经典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…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...

面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

Kafka入门-生产者
生产者 生产者发送流程: 延迟时间为0ms时,也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于:异步发送不需要等待结果,同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...
【Android】Android 开发 ADB 常用指令
查看当前连接的设备 adb devices 连接设备 adb connect 设备IP 断开已连接的设备 adb disconnect 设备IP 安装应用 adb install 安装包的路径 卸载应用 adb uninstall 应用包名 查看已安装的应用包名 adb shell pm list packages 查看已安装的第三方应用包名 adb shell pm list…...