写点什么

Leetcode 题目解析:274. H 指数

发布于: 刚刚
Leetcode题目解析:274. H 指数

一 摘要

H 指数问题感觉是 leetcode 中比较冷门的一道题目,至少在过去笔试面试的经历中都没有遇到过。不过仔细看了一下,重点在于对题目的理解,同时感觉也算是相对比较简单一点的中等难度题目。本系列文章会标明引用 leetcode 解析的部分内容,重点在于整理和阐述分析过程。

二 题目描述

引用 leetcode 的描述原文如下:

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

h 指数的定义:h 代表“高引用次数”(high citations),一名科研人员的 h 指数是指他(她)的 (n 篇论文中)总共有 h 篇论文分别被引用了至少 h 次。且其余的 n - h 篇论文每篇被引用次数 不超过 h 次。

例如:某人的 h 指数是 20,这表示他已发表的论文中,每篇被引用了至少 20 次的论文总共有 20 篇。

提示:如果 h 有多种可能的值,h 指数 是其中最大的那个。

三 题目解析

3.1 示例

输入:citations = [3,0,6,1,5]

输出:3

解释:给定数组表示研究者总共有 5 篇论文,每篇论文相应的被引用了 3, 0, 6, 1, 5 次。

  由于研究者有 3 篇论文每篇 至少 被引用了 3 次,其余两篇论文每篇被引用 不多于 3 次,所以她的 h 指数是 3。

3.2 分析

3.2.1 输入和输出

关于 h 的定义,题目中已经说的比较清楚。输入是一个整数数组,输出是数组对应的 h 值,这个值是唯一的。因为要的是“h 的多种可能的值中,最大的一个”。

3.2.2 计算方法分析

看到要计算的目标,是“最大”的一个,比较容易想到的是排序、贪心、动态规划等算法。而输入本身是一维整数数组,我们先尝试用对引用次数数组排序,并初始化 h 为 0,遍历引用次数数组来计算最大 h 的方法。

3.2.3 排序方法

使用的语言为 Java,java.util.Arrays 类中提供了对数组排序的方法,所以直接使用即可。代码及说明如下:

public class H1Solution {    public static int hIndex(int[] citations) {        // 数组升序排列        Arrays.sort(citations);        System.out.println(Arrays.toString(citations));        // 初始化i,记录当前遍历到的引用次数索引,从引用次数最大的开始        int i = citations.length - 1;        // 初始化h值为0        int h = 0;        while (i >= 0 && citations[i] > h) {            h++;            i--;        }        return h;    }
public static void main(String[] args){ int[] citations = {3,0,6,1,5}; int h = hIndex(citations); System.out.println(h); }}
复制代码

复杂度分析,数组长度为 n:

1、时间复杂度:O(nlogn),因为上述方法中要对数组进行排序,所以最快是 O(nlogn),“最快”的这点由 Arrays.sort()方法提供;因为后面是一次数组遍历,所以实际上复杂度为 O(nlogn+n),简化描述为 O(nlogn)

2、空间复杂度:O(logn),排序使用的额外空间,h 和 i 两个常量忽略不急。

3.2.4 计数排序

如果对上面的方法进行分析,就会发现算法的复杂度瓶颈在排序上。尽管 Arrays.sort()方法我们说了“最快”,但这是指基于比较的排序,所以最好的时间复杂度才是 O(nlogn)。但因为输入数组是整数数组,所以实际上是可以考虑其他方法来降低时间复杂度的。空间换时间,计数排序就是一种典型且适用于我们这个场景的方法。

引用 leetcode 解析的描述:

新建并维护一个数组 counter 来记录当前引用次数的论文有几篇,因为 h 不可能大于论文总篇数,所以对于引用次数超过论文发表数的情况,我们可以将其按照总的论文发表数来计算即可。这样我们可以限制参与排序的数的大小为 [0,n](其中 n 为总的论文发表数),使得计数排序的时间复杂度降低到 O(n)。

从后向前遍历数组 counter,对于每个 0≤i≤n,在数组 counter 中得到大于或等于当前引用次数 ii 的总论文数。当找到一个 H 指数时跳出循环,并返回结果。

public static int hIndex(int[] citations) {        int n = citations.length, tot = 0;        int[] counter = new int[n + 1];        for (int i = 0; i < n; i++) {            if (citations[i] >= n) {                counter[n]++;            } else {                counter[citations[i]]++;            }        }        for (int i = n; i >= 0; i--) {            tot += counter[i];            if (tot >= i) {                return i;            }        }        return 0;    }
复制代码


发布于: 刚刚阅读数: 2
用户头像

磨炼中成长,痛苦中前行 2017.10.22 加入

微信公众号【程序员架构进阶】。多年项目实践,架构设计经验。曲折中向前,分享经验和教训

评论

发布
暂无评论
Leetcode题目解析:274. H 指数