274. H 指数 [medium]

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

给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 h 指数。

h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的（N 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。（其余的 N - h 篇论文每篇被引用次数不超过 h 次。）

例如：某人的 h 指数是 20，这表示他已发表的论文中，每篇被引用了至少 20 次的论文总共有 20 篇。

示例：

输入：citations = [3,0,6,1,5]
输出：3 
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
     由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。
 

提示：如果 h 有多种可能的值，h 指数是其中最大的那个。

通过次数13,289 | 提交次数34,553

Second Try

2020-07-16

参考题解，使用画图法来理解，发现思路也是很清晰。

不过我的解法比官方题解考虑的条件要多一些，至少感觉比较符合自己的思维习惯。

注意论文数idx是从0开始的，因此不如直接就使用i + 1 进行比较，思维比较合理。

当刚好在交叉点的时候，返回 i + 1即可
当citations刚好比论文数少一点时，上一个citations应该比论文数多一点，返回上一个就行， returen i
最后如果每篇的citations非常高，比论文数多多了，那么直接返回论文数量即可。

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        # 按直方图法
        if not len(citations):
            return 0 
        citations = sorted(citations, reverse=True)
        for i in range(len(citations)):
            if citations[i] == i + 1:
                return i + 1
            elif citations[i] < i + 1:
                return i
        return len(citations)

执行用时：12 ms, 在所有 Python 提交中击败了97.69%的用户
内存消耗：13.1 MB, 在所有 Python 提交中击败了50.00%的用户

官方解法
https://leetcode-cn.com/problems/h-index/solution/hzhi-shu-by-leetcode/

public class Solution {
    public int hIndex(int[] citations) {
        // 排序（注意这里是升序排序，因此下面需要倒序扫描）
        Arrays.sort(citations);
        // 线性扫描找出最大的 i
        int i = 0;
        while (i < citations.length && citations[citations.length - 1 - i] > i) {
            i++;
        }
        return i;
    }
}

可能会出现多个不同的 hh 指数吗？

答案是否。从直方图中可以看出，由于 yy 轴已经降序排序，因此直线 y=xy=x 有且仅有穿过直方图一次。同时，也可以直接通过 hh 指数的定义证明出 hh 指数的唯一性

First Try

2020-07-16

思维不清楚，花了半个多小时才从一团乱麻中理出来。对于阶梯排序之类的棘手边界情况，练手还是不够多，思路容易一团乱麻。

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        """
        h指数： 总共有h篇文章被引用了至少h次？
        对于[3, 3, 3, 3, 3, 3]，总共有6篇文章被引用3次，那么h指数是多少？
        结果竟然也是3。
        那就是说至少有3篇文章被至少引用3次，而不是总共有3篇文章被至少引用3次。
        就因为这个，思维被搅乱了。
        """
        # 总共h篇文章被引用至少h次，限制的是确定的h篇文章，而引用次数只要大于等于h即可
        if not len(citations):
            return 0 
        counters = [0] * (max(citations) + 1)  #最大值
        for c in citations:
            counters[c] += 1
        # print('stage counter', counters)
        for i in range(len(counters) - 2, 0, -1):
            counters[i] += counters[i + 1]
        # print('check counter', counters)
        # i是引用次数，counters[i]是大于引用次数i的有多少本
        maxh = 0 
        for i in range(len(counters) - 1, 0, -1):
            maxh = max(maxh, min(i, counters[i]))
        return maxh 
        

执行用时：28 ms, 在所有 Python 提交中击败了34.68%的用户
内存消耗：12.7 MB, 在所有 Python 提交中击败了50.00%的用户

improved version

防止citations过高，导致空间利用率太低，把h最大限制为n本论文了。

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        # 计数法
        if not len(citations):
            return 0
        maxc = max(max(citations, len(citations))) + 1
        counters = [0] * maxc 
        for c in citations:
            counters[min(maxc, c)] += 1
        for i in range(maxc - 2, 0, -1):
            counters[i] += counters[i + 1]
        rv = 0
        for i in range(len(counters)):
            rv = max(rv, min(i, counters[i]))
        return rv 

执行用时：24 ms, 在所有 Python 提交中击败了57.23%的用户
内存消耗：13.1 MB, 在所有 Python 提交中击败了50.00%的用户