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

2504 ワード
LeetCode python
タイトルリンク
https://leetcode.com/problems/h-index-ii/
心得
274.H−Indexの後続の問題は,配列が秩序化されていると仮定した.前回のブログのやり方に従って、可能なh値ごとに遍歴して判断すると、時間の複雑度はO(n)であり、問題設定の要求O(logn)に合わない.この時間の複雑さの要求を見て、自然に二分法を思いついた.
hの定義に戻る:配列の中で1つの数字Hを見つけて、配列の中で少なくともHの数字がH以上で、残りの数字がH以下である.この配列が秩序配列である場合、この定義はさらに次のようになります.
hが定義に合致する場合、citations[len−h]≧h、すなわち配列中の少なくともH個の数字がH以上である.citations［len−h−1］≦h,すなわち残りの数はH以下である.ここではlen−h−1≧0という前提条件がある.ここでlenは配列サイズです.
さらに,hが定義に合致しない場合,citations[len−h]h:hはもっと大きいはずです.
この式ができてから、h値を判断したら、hが大きくなるべきか小さくなるべきかがわかります.このh値を二分法で見つけることができます.
ACコード
class Solution(object):
    def hIndex(self, citations):
        """ :type citations: List[int] :rtype: int """
        start, end = 1, len(citations)
        while start <= end:
            h = int((start+end)/2)
            if citations[len(citations)-h] < h: # h    
                end = h-1
            elif len(citations)-h-1>=0 and citations[len(citations)-h-1] > h: # h    
                start = h+1
            else:
                return h
        return 0

if __name__ == '__main__':
    s = Solution()
    array = [1,1]
    array.sort()
    print(s.hIndex(array))

問題を残す
タイトルには次のようなものがあります.
Note: If there are several possible values for h, the maximum one is taken as the h-index.
しかし二分法では,より小さなh値が取得され,プログラムが戻る場合がある.
この問題を避けるなら?それともこの問題は全然現れないのですか?教えてください.
あるコレクションで、このコレクションに記録されているランキングを検索します.
小議キーワードdelとインスタンスメソッド_del__(self)