力扣网编程274题:H指数之普通解法(中等)

一. 简介

本文记录力扣网上涉及数组,排序方面的编程题:H指数。

二. 力扣网编程274题:H指数(中等)

给你一个整数数组 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

解题思路一:(排序后统计)

题目是寻找最大的 h,使得至少有 h 篇论文被引用 ≥h 次。

首先,对数组进行降序排序,即从大到小排序;

其次,从左向右遍历数组,如果 citations[i]  > h 时,说明至少有 h+1篇文章引用次数 >= (h+1),因此可以安全的将 h自增1;

最后返回 h即为指数。

这种方法利用了排序后的特性:

当遍历到第 i 篇论文时,前面已经有 i 篇论文的引用次数 ≥ citations[i]。

如果 citations[i]  > h 时,说明至少有 h+1篇文章引用次数 >= (h+1)。

可以这里理解上面的特性:

    citations[i]:当遍历到第i个元素值citations[i],表示前 i+1 篇论文的引用次数 ≥ citations[i](降序数组的特性)。
    citations[i] > h,因此:
    前 i+1 篇论文的引用次数必然都 > h(因为它们 ≥ citations[i] > h)。
    此时,至少有 i+1 篇论文的引用次数 > h,即:
    至少有 i+1 篇论文的引用次数 ≥ h+1。


    如果 i+1 ≥ h+1(即当前遍历到的论文数量足够),则说明:
    存在 h+1 篇论文的引用次数 ≥ h+1,因此 H 指数可以更新为 h+1。

举例说明:

举个例子:如果某人有 5 篇论文,引用次数是 [3, 0, 6, 1, 5],排序后为[6,5,3,1,0]
从前往后看:第 1 篇(6)≥ 1 → 至少有 1 篇 ≥ 1第 2 篇(5)≥ 2 → 至少有 2 篇 ≥ 2第 3 篇(3)≥ 3 → 至少有 3 篇 ≥ 3第 4 篇(1)< 4 → 不满足 4 篇 ≥ 4

具体方法如下:

1. 首先初始化一个变量:h=0,来统计指数;

2. 其次,从大到小进行排序;

3. 从前往后遍历数组,判断 citations[i] > h,当满足时,h自增1。

4.循环退出,最后的 h即所求的指数;

C语言实现如下:

//从大到小排序
int small_to_large(const void* a, const void* b) {return *(int*)b- *(int*)a;
}int hIndex(int* citations, int citationsSize) {int i;int h = 0;qsort(citations, citationsSize, sizeof(int), small_to_large);for(i = 0; i < citationsSize; i++) {if(citations[i] > h) {h++;}}return h;
}

可以看出,排序解法的时间复杂度为 O (n log n)。

下一篇文章使用计数排序解法进行处理:

力扣网编程274题:H指数之计数排序(中等)-CSDN博客

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/pingmian/87895.shtml
繁体地址,请注明出处:http://hk.pswp.cn/pingmian/87895.shtml

如若内容造成侵权/违法违规/事实不符,请联系多彩编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

iptables防火墙,多IP环境下, 指定某个目的IP地址通过某个本地IP访问,策略路由!

需求在CentOS 7.9中&#xff0c;若需从特定源IP&#xff08;10.0.0.3&#xff09;访问目标网段 1.1.1.0/24方法一&#xff1a;策略路由&#xff08;支持网段&#xff09;1. 创建自定义路由表# 添加名为custom_table的路由表&#xff08;ID200&#xff09; echo "200 custo…

数字孪生技术引领UI前端设计新趋势:数据可视化与交互设计的深度融合

hello宝子们...我们是艾斯视觉擅长ui设计、前端开发、数字孪生、大数据、三维建模、三维动画10年经验!希望我的分享能帮助到您!如需帮助可以评论关注私信我们一起探讨!致敬感谢感恩!一、引言&#xff1a;数字孪生驱动 UI 设计的范式革新在大数据与三维可视化技术爆发的今天&…

【机器学习笔记 Ⅱ】6 激活函数

激活函数是神经网络的核心组件&#xff0c;其作用远不止“引入非线性”。以下是系统化的解析&#xff1a;1. 核心作用 (1) 引入非线性没有激活函数&#xff1a;多层神经网络等价于单层线性变换&#xff08;矩阵连乘仍是线性&#xff09;。加入激活函数&#xff1a;每层通过非线…

AI无标记动捕如何结合VR大空间技术打造沉浸式游戏体验

随着数字科技的迅猛发展&#xff0c;VR大空间技术正逐步成为各行业探索沉浸式体验的重要方向。在VR游戏领域&#xff0c;市场对于高度沉浸式体验的需求日益增长&#xff0c;而传统VR游戏主要依赖手柄和基础体感进行交互&#xff0c;而在VR大空间中&#xff0c;用户可以通过全身…

Qt智能指针

在 Qt 框架中&#xff0c;智能指针用于自动管理对象的生命周期&#xff0c;防止内存泄漏。以下是 Qt 中主要的智能指针及其用法详解&#xff1a;1. QScopedPointer作用&#xff1a;独占所有权&#xff0c;超出作用域时自动释放对象&#xff08;类似 std::unique_ptr&#xff09…

408第三季part2 - 计算机网络 - 信道利用率

理解t1是发送帧的传输时间t2是确认帧的传输时间中间是传播过程这整个过程就是发送周期任何题目会有以下几种情况题目这里数据帧和确认帧长度是一样的t1 t2然后把t1的传输数据算出来然后传播是0.2sd停止等待 k1确认帧忽略t2 0t1算好后&#xff0c;求数据帧的长度下面是速率&…

Android framework 开发者模式下,如何修改动画过度模式

Android framework 开发者模式下&#xff0c; 如何修改动画过度模式 开发者模式下&#xff0c;动画过度 模式1.0→0.5&#xff0c;按如下方式修改。 开发云 - 一站式云服务平台 .../core/java/com/android/server/wm/WindowManagerService.java | 8 ---- 1 file changed, …

win11安装paddlelabel并创建目标检测项目

创建虚拟环境 conda create -n paddlelabel python3.11.11 conda activate paddlelabel通过以下命令安装 pip install --upgrade paddlelabel输入命令pdlabel运行paddlelabel&#xff0c;发现报错&#xff1a; ModuleNotFoundError: Please install connexion using the flask …

关于Novatek B/G-R/G白平衡色温坐标系再探究

目录 一、准备知识 二、色温坐标系的构建 三、Novatek白平衡色温坐标系的再探究 2.1 直线白点框 2.2双曲线白点框 四、仿真代码 之前写的一篇博文关于联咏(Novatek )白平衡色温坐标系探究-CSDN博客感觉逻辑上有些混乱,这个周末我又好好思考了下,以…

基于路径质量的AI负载均衡异常路径检测与恢复策略

AI流量往往具有突发性、大象流&#xff08;大规模数据流&#xff09;占比高的特点&#xff0c;极易造成网络拥塞热点。一条质量不佳&#xff08;如高延迟、高丢包、带宽受限&#xff09;的路径&#xff0c;不仅自身无法有效传输数据&#xff0c;如果ECMP继续向其分发流量&#…

ubuntu22.04 安装cuda cudnn

1.输入nvidia-smi查看可以支持安装的cuda最大版本 2.cuda与cudnn版本的选择 核心原则 向下兼容性&#xff1a;较新的 cuDNN 通常兼容旧版 CUDA&#xff0c;但反之不成立 框架依赖&#xff1a;优先考虑深度学习框架&#xff08;TensorFlow/PyTorch&#xff09;的版本要求 硬件…

5、Receiving Messages:Message Listener Containers

提供了两个MessageListenerContainer实现&#xff1a; KafkaMessageListenerContainer ConcurrentMessageListener容器 KafkaMessageListenerContainer在单个线程上接收来自所有主题或分区的所有消息。ConcurrentMessageListenerContainer委托给一个或多个KafkaMessageListe…

JDBC 注册驱动的常用方法详解

JDBC 注册驱动的常用方法详解 在 JDBC 中&#xff0c;注册驱动是建立数据库连接的第一步。以下是几种常用的驱动注册方式&#xff1a; 1. 显式类加载&#xff08;传统方式&#xff09; // 通过 Class.forName() 加载驱动类 Class.forName("com.mysql.cj.jdbc.Driver&qu…

插入数据优化

目录 一.插入数据优化 1.insert语句优化 ①批量插入 ②手动提交事务 ③主键顺序插入 2.大批量插入数据&#xff08;100万条&#xff09; 举例 第一步&#xff1a;连接数据库时&#xff0c;加上--local-infile属性 第二步&#xff1a;查看全局参数local_infile的值&…

区块链在域名系统安全中的应用进展综述

一、区块链与DNS结合的核心原理1.1 传统DNS的安全缺陷中心化架构&#xff1a;传统DNS依赖中心化服务器&#xff08;如ICANN管理的根服务器&#xff09;&#xff0c;存在单点故障风险&#xff0c;易受DDoS攻击或配置错误影响。协议脆弱性&#xff1a;DNS协议设计之初缺乏加密和认…

GO Web 框架 Gin 完全解析与实践

目录 1. 为什么选择 Gin?解锁 Go Web 开发的超能力 Gin 的核心优势 什么时候用 Gin? 第一个 Hello World 2. 路由的艺术:从简单 GET 到复杂匹配 基础路由 高级路由技巧 性能优化小贴士 3. 中间件的魔法:让请求处理更聪明 内置中间件 自定义中间件 中间件的最佳实…

RabbitMQ使用topic Exchange实现微服务分组订阅

案例场景&#xff1a;用户下单后需要多个微服务&#xff08;如营销、会员&#xff09;分别订阅并处理订单事件&#xff0c;且每个微服务可能有多个集群实例&#xff0c;需要保证同一个微服务的集群中&#xff0c;只有一个实例消费到消息。不同于Kafka和rocketMQ有分组消费的功能…

kotlin 通道trysend方法

trySend 方法是 Kotlin 协程中 Channel 类的一个重要功能。它用于向通道发送元素&#xff0c;但与 send 方法不同的是&#xff0c;trySend 是非阻塞的。这意味着它不会在通道满时挂起当前协程&#xff0c;而是会立即返回。 trySend 方法的效果 非阻塞行为&#xff1a; 当你调用…

winform CheckedListBox单击选中解决方案

在WinForms的CheckedListBox控件中&#xff0c;默认需要双击才能切换选中状态&#xff08;复选框勾选&#xff09;。要实现单击即选中&#xff0c;需要通过代码处理鼠标点击事件并手动切换选中状态。以下是实现步骤&#xff1a; 1.CheckOnClick属性置为true即可。 2.通过事件处…

Docker文件操作、数据卷、挂载

一&#xff1a;容器文件操作 在Docker环境中&#xff0c;管理容器内部的文件是一个常见的需求。 无论是为了配置应用、备份数据还是调试问题&#xff0c;了解如何高效地进行文件操作都是非常重要的。 docker cp命令提供了一种简单的方法来在宿主主机和容器之间复制文件或目录…