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.length1 <= n <= 50000 <= 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& 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 = 0 n = len(citations) for i in range(n-1, -1, -1): if citations[i] > h: h += 1 return h3.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& citations) { int n=citations.size(); vector counter(n+1); int h=0; //计数排序 for(int i=0;in){ 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] += 1 else: counter[citation] += 1 for i in range(n, -1, -1): h += counter[i] # 引用至少 h 次的论文总数 if h >= i: # 这里的 i 代表引用次数 return i return 03.3 二分查找
设左边界为left，右边界为right，中点为mid。我们可以把原问题拆分成若干个子问题：判断至少有mid数大于mid。如果在区间[mid,right]满足，说明搜寻的h在右边，反之在左边。
平均时间复杂度O(n log n)，平均空间复杂度O(1)
class Solution { public: int hIndex(vector& citations) { return binarySearch(citations, 0, citations.size()); } private: int binarySearch(vector& 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) // 2 cnt = 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题
力扣官方题解