【面试经典150题】H 指数
题目链接
给你一个整数数组 citations ,其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
根据维基百科上 h 指数的定义:h 代表“高引用次数” ,一名科研人员的 h 指数 是指他(她)至少发表了 h 篇论文,并且每篇论文 至少 被引用 h 次。如果 h 有多种可能的值,h 指数 是其中最大的那个。
n == citations.length1 <= n <= 50000 <= 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…...
MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...
tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
企业如何增强终端安全?
在数字化转型加速的今天,企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机,到工厂里的物联网设备、智能传感器,这些终端构成了企业与外部世界连接的 “神经末梢”。然而,随着远程办公的常态化和设备接入的爆炸式…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...
uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...
Redis:现代应用开发的高效内存数据存储利器
一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发,其初衷是为了满足他自己的一个项目需求,即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源,Redis凭借其简单易用、…...
Golang——7、包与接口详解
包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...
Python竞赛环境搭建全攻略
Python环境搭建竞赛技术文章大纲 竞赛背景与意义 竞赛的目的与价值Python在竞赛中的应用场景环境搭建对竞赛效率的影响 竞赛环境需求分析 常见竞赛类型(算法、数据分析、机器学习等)不同竞赛对Python版本及库的要求硬件与操作系统的兼容性问题 Pyth…...
算法打卡第18天
从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。 示例 1: 输入:inorder [9,3,15,20,7…...
