[Array] LeetCode 274. H-index

1. Use sort O(nlogn)

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        citations = sorted(citations)

        result = 0

        for i in range(len(citations)):
            length = len(citations[i:])

            if length >= citations[i]:
                result = citations[i]
            elif citations[i] >= length:
                result = max(result, length)

        return result

Thinking Process

1. Sort the citations in ascending order.
2. If the length (including the current citation) is greater than or equal to the current citation, it means that we have at least h papers that have been cited at least h times, since the array is sorted in ascending order.
3. We also have to consider the case when the length is less than the current citation. For example, for [14, 15], the answer would be 2, since the length is less than the citation.

2. Use count sort O(n)

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        idx = 0
        count = [0] * (max(citations) + 1)

        for citation in citations:
            if citation:
                count[citation] += 1

        counter = 0
        for i in range(len(count) - 1, 0, -1):
            if count[i]:
                count[i] += counter
                counter = count[i]

        for citation in citations:
            if citation <= count[citation]:
                idx = max(idx, citation)
            elif citation > count[citation]:
                idx = max(idx, count[citation])

        return idx

Thinking Process

1. Slightly modify the count sort to solve the problem.
2. Set the size of count array to the maximum citation and add 1 for each citation.
3. Then, we iterate through the count array descendingly. If it has a citation, we add the counter to that count[citation] and update the counter to the value of the current citation counter = count[citation]. We do it this way because since we are iterating through it in a descending order, the bigger citation can cover up the smaller citations.
4. Last, we find the maximum h-index.