HIndex.java

import java.util.Arrays;

/**
 * https://leetcode.com/articles/h-index/
 */

/**
 * TestCase
 * [0]
 * [1]
 * []
 * [100]
 */
public class HIndex {

    // 耗时4ms，时间复杂度O(nlgn)
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int hIndex = 0;
        for (int i = citations.length - 1; i >= 0; i--) {
            hIndex = Math.max(hIndex, Math.min(citations.length - i, citations[i]));
        }
        return hIndex;
    }

    // 耗时1ms，时间复杂度O(n)
    public int hIndex2(int[] citations) {
        /**
         * 大于文章数的引用可以合并到一起
         */
        int n = citations.length;
        int[] f = new int[n + 1];
        for (int k : citations) {
            f[Math.min(k, n)]++;
        }
        int hindex = 0;
        /**
         * i表示引用数，j表示大于等于该引用数的总文章数
         */
        for (int i = n, j = 0; i >= 0; i--) {
            j += f[i];
            hindex = Math.max(hindex, Math.min(j, i));
        }
        return hindex;
    }
}