H-Index,H-Index II

1.H-Index

Total Accepted: 19058 Total Submissions: 70245 Difficulty: Medium

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."

For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

 (M) H-Index II

 

1.如果有序，题目的意思是, 

h = n-i;
citations[i] >= h 就符合要求

/*
0 1 4 5 6 7 9
*/

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        sort(citations.begin(),citations.end())    ;
        for(int i=0;i<n;i++){
            if(citations[i] >= n-i) return n-i;
        }
        return 0;
    }
};

 2.也可使用二分的思路来做，因为我们知道h的范围是[0,h]，而且每一个h都有固定的规则，那么就可以用二分来逼近答案

low=0,high=n+1;

while(low<high)
{
h=low+(high-low)/2;
统计citation>h的数量为y
如果有y=10篇大于等于h=citaton=8的文章,说明h不符合要求，也就是说我们选的citation太小了，我们把citation上移一个,即low=mid+1；
如果有y=4篇大于等于h=ciation=8的文章，转换一下就是所，有4篇papers的cication>=8，也就是我们选的citation太大了，把citation下移一个，high = mid-1;
如果相等，那么找到了
}
return low-1

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        if(n==0){
            return 0;
        }
        int low = 0;
        int high= n+1;
        while(low<high){
            int h = low+(high-low)/2;
            int y = 0;
            for(int i=0;i<n;i++){
                if(citations[i] >= h) y++;
            }
            if(y == h){
                return h;
            }else if(y<h){
                high = h;
            }else{
                low = h+1;
            }
        }
        return low-1;
    }
};

 2.H-Index II

Total Accepted: 13860 Total Submissions: 43755 Difficulty: Medium

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        int low_index = 0;
        int high_index= n-1;
        while(low_index<=high_index){
            int y = low_index+(high_index-low_index)/2;
            int h = n-y;
            if(citations[y] == h){
                return h;
            }else if(citations[y] < h){
                low_index = y+1;
            }else{
                high_index = y-1;
            }
        }
        return n==0 ? 0 : n-low_index;
    }
};