274. H-Index (Medium)

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 indexhifhof his/herNpapers have at least h citations each, and the otherN − hpapers have no more than hcitations each."

For example, givencitations = [3, 0, 6, 1, 5], which means the researcher has5papers in total and each of them had received3, 0, 6, 1, 5citations respectively. Since the researcher has3papers withat least3citations each and the remaining two with no more than3citations each, his h-index is3.

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

Solution 1: Counting Sort O(n); O(n)

https://leetcode.com/problems/h-index/solution/

    /**
     * Counting Sort O(n); O(n)
     * Suppose n is the number of papers.
     * H can be at most n when a person has n papers and all of them have more than n citations.
     * To find a number h that h of his n papers have >= h citations, put papers in buckets.
     * All papers have >= n citations put into bucket n.
     * Papers have i citations put into bucket i.
     * Then count backwards.
     * The first number i that has total papers >= i is the answer.
     */
    public int hIndex(int[] citations) {
        if (citations == null || citations.length == 0) {
            return 0;
        }

        int n = citations.length;
        int[] papers = new int[n + 1]; //index: the number of papers' citations, value: the paper counts
        for (int c : citations) {
            if (c >= n) {
                papers[n]++;
            } else {
                papers[c]++;
            }
        }

        int paperSum = 0;
        for (int i = n; i >= 0; i--) {
            paperSum += papers[i];
            if (paperSum >= i) {
                return i;
            }
        }
        return 0;
    }

Follow Up:

1. Given一个unsorted array， find the greatest natural number N, such that, there exists at least N numbers in the array which are greater or equal to N 比如input是【5，5，5】的话，output是3