面试经典150题 day11
- 题目来源
- 我的题解
- 方法一 排序+从后往前遍历
- 方法二 计数排序+后缀和
- 方法三 排序+从左到右遍历
题目来源
力扣每日一题;题序:274
我的题解
方法一 排序+从后往前遍历
先将数组升序排序,然后h从n到0开始遍历,计算被引用次数大于等于 h的论文数
时间复杂度:O(nlogn)
空间复杂度:O(1)
public int hIndex(int[] citations) {
int n=citations.length;
Arrays.sort(citations);
int count=0;//表示h值时,被引用次数大于等于 h的论文数
int index=n;//表示h值
for(int i=n-1;i>=0;i--){
//当引用值大于h时,需要将count加1
if(citations[i]>=index)
count++;
else{
//若被引用次数大于等于 h的论文数大于h则直接返回h值,因为是从大往小遍历的
if(count>=index)
return index;
//更新h值
while(citations[i]<index&&count<index)
index--;
//当引用值大于h时,需要将count加1
if(citations[i]>=index)
count++;
}
}
//返回最终的h值
return index;
}
方法二 计数排序+后缀和
先计算每个引用次数出现的次数(引用次数大于n的作为n处理),然后计算器后缀和,只要suf[i]>=i则返回i,否则继续求前缀和。
时间复杂度:O(n)
空间复杂度:O(n)
public int hIndex(int[] citations) {
int n=citations.length;
int[] count=new int[n+1];
for(int i=0;i<n;i++){
if(citations[i]>=n)
count[n]++;
else
count[citations[i]]++;
}
for(int i=n;i>=0;i--){
if(i!=n)
count[i]+=count[i+1];
if(count[i]>=i)
return i;
}
return 0;
}
方法三 排序+从左到右遍历
直接先排序,并将h初始设置为0,每当末尾的满足 citations[right]>h时,h加一。
时间复杂度:O(nlogn)
空间复杂度:O(1)
public int hIndex(int[] citations) {
Arrays.sort(citations);
int h=0;
int right=citations.length-1;
while(right>=0&&citations[right]>h){
h++;
right--;
}
return h;
}
有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈😄~