[LeetCode]H-Index

题目描述:

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-index from a plot of decreasing citations for numbered papers

题目大意:

给定研究人员的文章引用次数的数组(每一篇文章的引用次数都是非负整数),编写函数计算该研究人员的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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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

Pingbacks已关闭。

评论
  1. Tina Tina 发布于 2016年6月5日 09:37 #

    解法二是O(n+logn) 吧?

  2. 在线疯狂 在线疯狂 发布于 2016年6月8日 20:46 #

    排序的复杂度是O(n * log n)

张贴您的评论