leetcode 274. H-Index-h因子|哈希表

原题链接：274. H-Index

【思路-Java】T=O(nlogn)|M=O(1)

论文里的 h 因子判定，题目的意思可能有点晦涩。h 因子是评判学术成就的一种重要方法，h 因子越高越好，h 因子兼顾研究学术人员的学术产出数量与学术产出质量。假设一个研究者的 h 因子为 10，则表明该研究者被引用次数大于等于 10 的文章数量也应大于等于 10。

明白了 h 因子意思，我们看题目给定实例 citations = [3, 0, 6, 1, 5]，为什么是3呢？因为引用次数大于等于3的文章为citations = [3, 0, 6, 1, 5]，蓝颜色部分，显然判定该学者 h 因子为6或者5是不合适的。

 对于本思路，先将数组排序。然后对于每个引用次数，比较大于该引用次数的文章，去引用次数和文章数的最小值，即 Math.min(citations.length-i, citations[i])，并更新 level，取最大值。

当然这题排好序之后可以用二分查找进行遍历，这样速度会更快，

该方法可以参考我的另一篇博文：leetcode 275. H-Index II-h因子|二分查找

public class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int level = 0;
        for(int i = 0; i < citations.length; i++)
            level = Math.max(level,Math.min(citations.length - i,citations[i]));
        return level;
    }
}

81 / 81  test cases passed. Runtime: 3 ms  Your runtime beats 33.75% of javasubmissions.

【思路2-Java、Python】T=O(n)|M=O(n)

题目提示可以借用 hash 表降低复杂度，我们使用一个大小为 n+1 的数组 count。对于用数组建立的 hash 表，我们必须要弄懂数组下标和数组值所表示的含义， 对于 count[i]表示的是引用数为 i 的文章数量。从后往前遍历数组，当满足 count[i] >= i 时，i 就是 h 因子，返回即可，否则返回0。

为什么要从后面开始遍历？ 为什么 count[i] >= i 时就返回？

一方面引用数引用数大于 i-1 的数量是i-1及之后的累加，必须从后往前遍历。另一方面，h 因子要求尽可能取最大值，而 h 因子最可能出现最大值的地方在后面，往前值只会越来越小，能尽快返回就尽快返回，所以一遇到 count[i] >= i 就返回。

public class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] count = new int[n + 1];
        for(int c : citations)
            if(c >= n) count[n]++;  //当引用数大于等于 n 时，我们均将其数量计入 count[n]中
            else count[c]++;
        for(int i = n; i > 0; i--) {  //从后面开始遍历
            if(count[i] >= i) return i;
            count[i-1] += count[i];  //引用数大于 i-1 的数量是i-1及之后的累加
        }
        return 0;
    }
}

81 / 81  test cases passed. Runtime: 1 ms  Your runtime beats 59.80% of javasubmissions.

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        n = len(citations)
        count = [0] * (n + 1)
        for c in citations :
            if c >= n : count[n] += 1
            else : count[c] += 1
        for i in range(1, n + 1)[::-1] :
            if count[i] >= i : return i
            count[i-1] += count[i]
        return 0

81 / 81  test cases passed. Runtime: 52 ms  Your runtime beats 43.05% of pythonsubmissions.