h指数

题目

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。

根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且每篇论文 至少 被引用 h 次。如果 h 有多种可能的值，h 指数 是其中最大的那个。

解答

1. 排序

class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);//按照升序排序
        int i;
        int k=1;
        for(i=citations.length-1;i>=0;i--){
            if(citations[i]<k){
                break;
            }
            k++;
        }
        return k-1;
    }
}

2. 计数排序
   统计每一种引用数，有几篇论文

Class Solution{
    public int hIndex(int []citations){
        int n=citations.length;
        int counter[]=new int [n+1];
        for(int i=0;i<n;i++){
            if(citations[i]>=n){
                counter[n]++;
            }
            else{
                counter[citations[i]]++;
            }
        }
        int tot=0;
        for(int i=n;i>0;i--){
            tot+=counter[i];
            if(tot>=i){
                return i;
            }
        }
        return 0;
    }
}

3. 二分查找
   它是满足「有 h 篇论文的引用次数至少为 h」的最大值。小于等于 h 的所有值 x 都满足这个性质，而大于 h 的值都不满足这个性质

class Solution {
    public int hIndex(int[] citations) {
        int left=0,right=citations.length;
        int mid=0,cnt=0;
        while(left<right){
            // +1 防止死循环
            mid=(left+right+1)>>1;
            cnt=0;
            for(int i=0;i<citations.length;i++){
                if(citations[i]>=mid){
                    cnt++;
                }
            }
            if(cnt>=mid){
                // 要找的答案在 [mid,right] 区间内
                left=mid;
            }else{
                // 要找的答案在 [0,mid) 区间内
                right=mid-1;
            }
        }
        return left;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/h-index/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。