[LeetCode]274. H-index

Question

每一个科学家的h-index是这样定义的：假设他发表的文章是一个数组，那么数组中的值代表的是他这篇文章被引用数，比如[3,0,6,1,5]代表的是他有五篇文章，每篇文章的被引用数分别是3，0，6，1，5
H-index如果是N，就是说他至少有N篇文章的引用数不少于N，而且剩下的文章的引用数都是少于N的，在这个例子中就是3，因为他的3,6,5这三篇文章的引用数都不少于3，而且剩下的文章的引用数都没有达到3

Solution

这道题的关键思路是如何把这个citations数组用另一种方式表示。
在这里就是利用了Bucket Sort的思想

Bucket Sort，也叫基数排序，是通过判断每一位数字的大小，分别按位数从高到低排序。

在这里我们可以定义一个长度为length+1的list,这个list的每一个值的index就是被引用数，比如上面的例子就会变成[1,1,0,1,0,1,1]，为什么长度是length+1呢，因为有可能文章的被引用数比总文章数还多，这种情况我们就把它分配到index为length的位置上

最后我们从尾到头遍历这个数组，将每个index上的值依次累加，如果累加的和是比index要大的，说明满足了H-index的条件，而且这个index就是最大的H-index

Code

#coding: utf-8
class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        bucket_list = []#bucket_list就是代表在那个index的paper的citaion数就是index的值
        l = len(citations)
        for i in range(l+1):
            bucket_list.append(0)
        for i in citations:
            if i >= l:
                bucket_list[l] += 1
            else:
                bucket_list[i] += 1
        j = l
        accumulate = 0
        while j > 0:
            accumulate = accumulate + bucket_list[j]
            if accumulate >= j:
                return j
            j-=1
        return 0

Extension

Bucket Sort
桶排序分为高位桶(MSD)和低位桶(LSD)，是个稳定的排序算法，时间复杂度为O(n + radix)

bucketSort

Question

Solution

Code

Extension

FEATURED TAGS

FRIENDS