LeetCode面试150——274H指数

题目难度：中等

默认优化目标：最小化平均时间复杂度。

Python默认为Python3。

目录

1 题目描述

2 题目解析

3 算法原理及代码实现

3.1 排序

3.2 排序时间优化(计数排序)

3.3 二分查找

参考文献

---

1 题目描述

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

提示：

• n == citations.length

• 1 <= n <= 5000

• 0 <= citations[i] <= 1000

2 题目解析

输入是数组citations(引用的英文)，输出是h指数。citations的长度n代表总共发表的论文篇数，下标代表论文名，元素值代表论文被引用的次数。

h指数的意思为，citations中有h篇论文被引用次数超过了h次。如示例2中，h取1，至少发表了一篇论文引用次数超过1，h指数为1。h取2，至少发表了2篇论文引用次数超过2，不成立。h取3，至少发表了3篇论文引用次数超过3，不成立。

暴力求法是先计算citations长度n，然后每个元素去和n比大小，都大于则输出n，否则接着和n=n-1比大小，以此类推。平均时间复杂度为O(n!)。

3 算法原理及代码实现

3.1 排序

在暴力求法的基础上，我们先对citations排序，变成一个有序数组。假如是升序排序，一次循环从后向前遍历。

题目中至少就是大于的意思，比如至少大于 1次就是>0，至少大于h次就是>h。因此初始化h=0。citations[i]和h比大小，如果citations[i]大于h，h++，反之不执行任何操作。最后输出h即可。

平均时间复杂度为O(n log n)(采用快排)，平均空间复杂度为O(1)。

C++代码实现

class Solution {
public:int hIndex(vector<int>& citations) {int n=citations.size();int h=0;
​sort(citations.begin(),citations.end());
​for(int i=n-1;i>=0;i--){if(citations[i]>h){h++;}}
​return h;
​}
};

Python代码实现

class Solution:def hIndex(self, citations: List[int]) -> int:citations.sort()h = 0n = len(citations)for i in range(n-1, -1, -1):if citations[i] > h:h += 1return h

3.2 排序时间优化(计数排序)

从3.1可以看到，平均时间复杂度和排序算法的时间复杂度相同。我们可以牺牲空间换时间，使用计数排序进一步降低时间复杂度。

新建一个计数数组counter，将citations中论文引用次数映射到counter中。映射规则如下：如果元素值大于n，counter[n]++；反之，对应引用次数的下标位置citations[i]，计数数组counter[citations[i]]++。

平均时间复杂度为O(n)，平均空间复杂度为O(n)。

C++代码实现如下

class Solution {
public:int hIndex(vector<int>& citations) {int n=citations.size();vector<int> counter(n+1);int h=0;
​//计数排序for(int i=0;i<n;i++){if(citations[i]>n){counter[n]++;}else{counter[citations[i]]++;}}
​for(int i=n;i>=0;i--){h+=counter[i];//引用至少h次的论文总数if(h>=i){//这里的i代表引用次数return i;}}
​return 0;
​}
};

Python代码实现

class Solution:def hIndex(self, citations: List[int]) -> int:n = len(citations)counter = [0] * (n + 1)h = 0
​# 计数排序for citation in citations:if citation > n:counter[n] += 1else:counter[citation] += 1
​for i in range(n, -1, -1):h += counter[i]  # 引用至少 h 次的论文总数if h >= i:  # 这里的 i 代表引用次数return i
​return 0

3.3 二分查找

设左边界为left，右边界为right，中点为mid。我们可以把原问题拆分成若干个子问题：判断至少有mid数大于mid。如果在区间[mid,right]满足，说明搜寻的h在右边，反之在左边。

平均时间复杂度O(n log n)，平均空间复杂度O(1)

class Solution {
public:int hIndex(vector<int>& citations) {return binarySearch(citations, 0, citations.size());}
​
private:int binarySearch(vector<int>& citations, int left, int right) {if (left >= right) {return left;}
​int mid = (left + right + 1) >> 1;int cnt = 0;for (int i = 0; i < citations.size(); i++) {if (citations[i] >= mid) {cnt++;}}
​if (cnt >= mid) {return binarySearch(citations, mid, right);} else {return binarySearch(citations, left, mid - 1);}}
};
​

Python代码实现

class Solution:def hIndex(self, citations: List[int]) -> int:return self.binarySearch(citations, 0, len(citations))
​def binarySearch(self, citations, left, right):if left >= right:return left
​mid = (left + right + 1) // 2cnt = sum(1 for citation in citations if citation >= mid)
​if cnt >= mid:return self.binarySearch(citations, mid, right)else:return self.binarySearch(citations, left, mid - 1)
​

参考文献

力扣面试经典150题

力扣官方题解