Leetcode: 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.

Show Hint 

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Hide Tags

 Hash Table Sort

Hide Similar Problems

 (M) H-Index II

-----------------------------------------------------------

----------------------------------------------------------

Sort and check, that's all for a convenient way. 

To reduced the time, we don't need to sort the whole array, we can sort one then check one. E.g.,when using bubble sort, we can find out the minimal one then check the h value, find the next minimal value then check the h value, ......., until the real h is found. If no is found, then h=0. The testing results highly depend on the testing case. 

e.g. 

1    2    2     3     3   citations 

5   4     3     2     1   potential H index

check from left to right, when citation[i]>=potential[i], return length-i. 

OR

e.g. 

1    2    2     3     3   citations 

1   2     3     4     5   potential H index

check from right to left, when citation[i]>=potential[i], return i. 

///////////////////////////////////////////////

//code

class Solution {

public:

       int hIndex(vector<int>& citations) {

              //check input

              int len = citations.size();

              //if (len==0) return 0;

              //bubble sort and judge

              for (int i = 0; i<len; i++){

                     for (int j = len - 1; j>i; j--){

                           if (citations[j]<citations[j - 1]) swap(citations[j], citations[j - 1]);

                     }

                     //judge h

                     if (citations[i] >= len - i)return len - i;

              }

              return 0;

       }

};