Leetcode Study Day 7

H-Index

Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return the researcher’s h-index.

According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.

Example 1:

Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] 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, their h-index is 3.

Example 2:

Input: citations = [1,3,1]
Output: 1
 

Constraints:

n == citations.length
1 <= n <= 5000
0 <= citations[i] <= 1000

My solution

My idea is firstly sort the array first from the least to the largest.

sort (citations.begin(), citations.end(), [](int & a, int & b){
    return a <= b;
});

Also, we create two variables, one is the hIndex and the other is called count. For the situation that the ith element is one of the h-index, which means i + citations[i] is smaller than the length of the citations array, during the iteration, we update the maximum h-index.
For example, in the array 0,1,3,5,6, 0 is one h-index; 1 is one h-index and it means the researcher has published at least 1 paper that has been cited at least 1 time; 3 is one h-index and it means the researcher has published at least 3 paper that has been cited at least 3 times, when we count i + citations[i], which is 2 + 3, the result is equal to the length of the array. So we update the h-index to 3.

In the loop:
    if ((citations[i] > hInd) && (i + citations[i]) <= n){
        hInd = citations[i];
    }

However, there exists some situation that not fit this method, for example, the array [0,0,4,4].
In this situation, our h-index is 0, however, the correct answer is 2 because the researcher has published 2 papers that have been cited at least 2 times. So I use the variable count to handle this situation, once the result of i + citations[i] is larger than the length of the array, we add one to the count.

In the loop:
    if (i + citations[i] >n)
        count ++;

After iteration, we return the larger one between the h-index and the count.

Full code

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