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.
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
1 public class Solution { 2 public int hIndex(int[] citations) { 3 int[] res = new int[citations.length]; 4 mergesort(citations,res,0,citations.length-1); 5 for(int i=0;i<citations.length;i++){ 6 if(i>=citations[i]){ 7 return i; 8 } 9 } 10 return citations.length; 11 } 12 public void mergesort(int[] citations,int[] res,int start,int end){ 13 if(start>=end) return; 14 int mid = start+(end-start)/2; 15 mergesort(citations,res,start,mid); 16 mergesort(citations,res,mid+1,end); 17 combine(citations,res,start,mid+1,end); 18 } 19 public void combine(int[] citations,int[] res,int left,int mid,int right){ 20 int left_start = left; 21 int left_end = mid-1; 22 int right_start = mid; 23 int right_end = right; 24 int k = left_start; 25 while(left_start<=left_end&&right_start<=right_end){ 26 if(citations[left_start]>=citations[right_start]){ 27 res[k++] = citations[left_start++]; 28 }else{ 29 res[k++] = citations[right_start++]; 30 } 31 } 32 while(left_start<=left_end){ 33 res[k++] = citations[left_start++]; 34 } 35 while(right_start<=right_end){ 36 res[k++] = citations[right_start++]; 37 } 38 for(int i=left;i<=right;i++){ 39 citations[i] = res[i]; 40 } 41 } 42 } 43 //the run time complexity could be O(nlogn) ,the space complexity could be O(n);