免费建设网站和域名,上海城隍庙旅游区,wordpress图片暗箱,信息流广告是什么意思?题目难度#xff1a;中等
默认优化目标#xff1a;最小化平均时间复杂度。
Python默认为Python3。 目录
1 题目描述
2 题目解析
3 算法原理及代码实现
3.1 排序
3.2 排序时间优化(计数排序)
3.3 二分查找
参考文献 1 题目描述
给你一个整数数组 citations #xf…题目难度中等
默认优化目标最小化平均时间复杂度。
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至少发表了一篇论文引用次数超过1h指数为1。h取2至少发表了2篇论文引用次数超过2不成立。h取3至少发表了3篇论文引用次数超过3不成立。
暴力求法是先计算citations长度n然后每个元素去和n比大小都大于则输出n否则接着和nn-1比大小以此类推。平均时间复杂度为O(n!)。 3 算法原理及代码实现
3.1 排序
在暴力求法的基础上我们先对citations排序变成一个有序数组。假如是升序排序一次循环从后向前遍历。
题目中至少就是大于的意思比如至少大于 1次就是0至少大于h次就是h。因此初始化h0。citations[i]和h比大小如果citations[i]大于hh反之不执行任何操作。最后输出h即可。
平均时间复杂度为O(n log n)(采用快排)平均空间复杂度为O(1)。
C代码实现
class Solution {
public:int hIndex(vectorint citations) {int ncitations.size();int h0;
sort(citations.begin(),citations.end());
for(int in-1;i0;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中。映射规则如下如果元素值大于ncounter[n]反之对应引用次数的下标位置citations[i]计数数组counter[citations[i]]。
平均时间复杂度为O(n)平均空间复杂度为O(n)。
C代码实现如下
class Solution {
public:int hIndex(vectorint citations) {int ncitations.size();vectorint counter(n1);int h0;
//计数排序for(int i0;in;i){if(citations[i]n){counter[n];}else{counter[citations[i]];}}
for(int in;i0;i--){hcounter[i];//引用至少h次的论文总数if(hi){//这里的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(vectorint citations) {return binarySearch(citations, 0, citations.size());}
private:int binarySearch(vectorint 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题
力扣官方题解
