题目难度:中等
默认优化目标:最小化平均时间复杂度。
Python默认为Python3。
目录
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 = 0 n = len(citations) for i in range(n-1, -1, -1): if citations[i] > h: h += 1 return 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] += 1 else: 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) // 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)