274. H-Index

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.

Solution:

1. Sort the citations, check from highest to lowest and see if current citation is greater than visited papers, continue if the statement is true.

 public int hIndex(int[] citations) {  
     Arrays.sort(citations);  
     int res=0;  
     for(int i=citations.length-1;i>=0;i--){  
       if(citations[i]<res+1) break;  
       else res++;  
     }  
     return res;  
   }  

2. O(n) solution
DP.
For example, [3, 0,6,1,5], the total amount of paper is 5, so the maximum possible h-index is 5. We use an array h to keep track the count of papers that has the citations as the current index. For any paper that has citations greater than 5, we increment h[5].
So the h will look like this[1,1,0,1,0,2] , we have 2 paper that has citations>=5, 5 is not our h index, we have 2+0 papers that has citations >=4, 4 is not h index, we have 2+0+1=3 papers that has citations>=3, so 3 is our h-index.

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