面试经典150题——H指数

题目来源

力扣每日一题；题序：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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

方法二 计数排序+后缀和

先计算每个引用次数出现的次数（引用次数大于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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方法三 排序+从左到右遍历

直接先排序，并将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;
}
1
2
3
4
5
6
7
8
9
10

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈