LeetCodeブラシ問題(Python)|274.H-Index

タイトルリンク
https://leetcode.com/problems/h-index/
心得
とても面白いテーマで、H因子を計算します.
まずH因子の定義を抽象化し,配列中に少なくともH個の数字がH以上であり,残りの数学がH以下であるように,配列中に1つの数字Hを見つけた.
解析問題で与えられた例[3,0,6,1,5].Hの値範囲は0〜5であることが明らかである.最も暴力的な方法は、満足しているかどうかを一つ一つ判断することだ.では,いずれの可能な値に対しても,Hの条件を満たすか否かを判断するために配列を1回巡回する.従って時間複雑度はO(n 2)である.
配列が整列配列であれば?では,いずれかの可能な値について,O(1)時間でこの値がHの定義を満たすか否かを判断できる.したがって,配列を並べ替えて逐一判断すると,総時間複雑度はO(nlogn)に低下する.
ACコード

class Solution(object):
    def hIndex(self, citations):
        """ :type citations: List[int] :rtype: int """
        citations.sort(reverse=False)
        h = len(citations)
        index = 0
        while index < len(citations):
            if citations[index] >= h:
                return h
            index += 1
            h -= 1
        return 0

if __name__ == '__main__':
    s = Solution()
    print(s.hIndex([3, 0, 6, 1, 5]))