274. H指数

Problem: 274. H 指数

思路

看到题目中有至少h篇大于等于h这样的比大小字样，可以想到排序数组，这样可以使数组具有单调性。

将数组从大到小排序，用指针i遍历数组，如果有第i大的引用小于i + 1（个数），那么显然就不存在i + 1个大于等于i + 1的文章（之后的文章都比它小），这样所求的i就是H指数。

复杂度

• 时间复杂度: $O(nlogn)$，排序的时间消耗，在本题里数据范围较小，如果使用计数排序可以降到$O(n+k)$
• 空间复杂度: $O(1)$，只需若干常量。

Code

[]

class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int n = citations.length;
        for (int i = n - 1; i >= 0; i--) {
            if (citations[i] < n - i) {
                return n - i - 1;
            }
        }
        return n;
    }
}