LeetCode 274.

Question

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.

Intuition

The answer must be located in the range:

0 <= answer <= Math.min(citations.length, Max(citations[i]))

Then, I try Binary Search (usually the time complexity of BS solution is O(nlogn))

Approach

The initial left and right value should be:

left = 0 or 1 (if the minimum length of citations is 1)
right = Math.min(citations.length, Max(citations[i]))

Complexity

Time complexity: O(nlogn)
Space complexity: O(1)

Code

class Solution {
    public static int hIndex(int[] citations) {
        int max = -1;
        for (int c: citations) {
            max = Math.max(max, c);
        }
        int left = 0, right = Math.min(citations.length, max);
        int count;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            count = 0;
            for (int c: citations) {
                if (c >= mid) {
                    count++;
                }
            }
            if (count < mid) {
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return left - 1;
    }
}

Check out the description of these two problems at LC 274.