LeetCode面试150——274H指数

avatar
作者
筋斗云
阅读量:0

题目难度:中等

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

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 = 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) ​

参考文献

力扣面试经典150题

力扣官方题解

广告一刻

为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!