1.19 H-Index

Description

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.

Hint:

An easy approach is to sort the array first. What are the possible values of h-index? A faster approach is to use extra space.

Method

sort firstly and then check each element to find the h value

second method use extra space use a array to calculate the number of papers for each citations. and then accumulate from the highest citation to check whether it fulfills requirements, that there are h papers that has at least h citations.

Time and Space Complexity

o(nlogn + n) o(n)

Code

public class Solution {

    public int hIndex(int[] citations) {
       if (citations == null || citations.length == 0){
           return 0;
       }
       Arrays.sort(citations);
       int n = citations.length;

       int res = citations[0] >= n ? n : 0;
       for (int i = 1; i < citations.length; i++){
            if (n - i <= citations[i] && citations[i - 1] <= n - i){
                res = n - i;
            }
       }
       return res;
}

}

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

          for (int i = length; i >= 0; i--){
               t += arr[i];
               if (t >= i){
                   return i;
               }
          }
          return 0;
   }