274.H-Index

Tags: [bucket_sort], [sort], [trick]

Com: {fb}

Link: https://leetcode.com/problems/h-index/#/description

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 otherN − h papers have no more than h citations each."

For example, givencitations = [3, 0, 6, 1, 5], which means the researcher has5papers in total and each of them had received3, 0, 6, 1, 5citations respectively. Since the researcher has3papers withat least3citations each and the remaining two withno more than3citations each, his h-index is3.

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

Solution: Bucket Sort

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        if not citations:
            return 0

        buckets = [0 for _ in xrange(len(citations) + 1)]
        for c in citations:
            if c > len(buckets) - 1:
                buckets[-1] += 1
            else:
                buckets[c] += 1

        tmp = 0
        for i in xrange(len(buckets) - 1, -1, -1):
            tmp += buckets[i]
            if tmp >= i:
                return i

        return 0

Solution: Sort, Find Max Square

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        if not citations:
            return 0

        citations.sort(key=lambda x: -x)
        for i in xrange(len(citations) - 1, -1, -1):
            bottom_len = i + 1
            if citations[i] >= bottom_len:
                return bottom_len

        return 0

Revelation:

• Find the max area square. Be careful of the case citations = [100]

Note:

• Time complexity = O(nlgn), n is the number of citations.
• Space complexity = O(1).