题目描述：

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 index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."

For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.

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

题目大意：

给定研究人员的文章引用次数的数组（每一篇文章的引用次数都是非负整数），编写函数计算该研究人员的h指数。

根据维基百科对h指数的定义：“一名科学家的h指数是指其发表的N篇论文中，有h篇论文分别被引用了至少h次，其余N-h篇的引用次数均不超过h次”。

例如，给定引用次数数组 = [3, 0, 6, 1, 5]，这意味着研究人员总共有5篇论文，每篇分别获得了3, 0, 6, 1, 5次引用。由于研究人员有3篇论文分别至少获得了3次引用，且其余两篇的引用次数不超过3次，因而其h指数是3。

注意：如果存在多个可能的h值，取最大值作为h指数。

解题思路：

h指数综合考虑研究人员的文章篇数与引用次数，来评价其学术成就。

解法I：O(n) 统计 + 遍历

使用长度为N + 1的数组cnts记录引用次数在0 ~ N（N篇以上的记为N）的文章个数

然后遍历cnts数组，计算h值的最大值

Python代码：

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

解法II：O(n * logn) 排序 + 遍历

(1)：按照文章引用次数倒序排列，循环遍历数组，统计下标i小于引用次数c的文章篇数即可。

Python代码：

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        for i, c in enumerate(sorted(citations, reverse = True)):
            if i >= c:
                return i
        return len(citations)

使用sum函数，上述代码可以缩减为一行。

Python代码：

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        return sum(i < c for i, c in enumerate(sorted(citations, reverse = True)))

(2)：按照文章引用次数正序排列，循环遍历数组，统计min(引用次数c, 剩余文章篇数N-i)的最大值

Python代码：

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        N = len(citations)
        for i, c in enumerate(sorted(citations)):
            if N - i <= c:
                return N - i
        return 0

使用max函数，上述代码可以缩减为一行。

Python代码：

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        return max(min(c, len(citations) - i) 
                for i, c in enumerate(sorted(citations) + [0]))

 

本文链接：http://bookshadow.com/weblog/2015/09/03/leetcode-h-index/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码