H-Index Problem


Description

LeetCode Problem 274.

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

According to the definition of h-index on Wikipedia: A scientist has an index h if h of their n papers have at least h citations each, and the other n − h papers have no more than h citations each.

If there are several possible values for h, the maximum one is taken as the h-index.

Example 1:

1
2
3
4
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:

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

Constraints:

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


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int len = citations.size();
        sort(citations.begin(), citations.end());

        if (len == 1)
            return (citations[0] == 0) ? 0 : 1;
        
        int left = 0, right = len-1;
        int mid;

        while (left <= right) {
            mid = (left + right) / 2;
            if (citations[mid] == (len-mid))
                return len-mid;
            else if (citations[mid] < (len-mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
            
        }
        return len-left;
    }
};




Related Posts

Largest Number At Least Twice Of Others Problem

LeetCode 747. You are given an integer array nums where...

Third Maximum Number Problem

LeetCode 414. Given an integer array nums, return the third...

Queue Reconstruction By Height Problem

LeetCode 406. You are given an array of people, people,...

Minimum Moves To Equal Array Elements II Problem

LeetCode 462. Given an integer array nums of size n,...

Assign Cookies Problem

LeetCode 455. Assume you are an awesome parent and want...