Python O(n) and 2 line O(nLogn) solutions


  • 0
    D

    O(n) Solution:

    class Solution(object):  
        def hIndex(self, citations):  
            """ 
            :type citations: List[int] 
            :rtype: int 
            """  
            n = len(citations)  
            equal_h = [0] * (n+1)  
            for h in range(n):  
                if citations[h] >= n: equal_h[n] += 1  
                else: equal_h[citations[h]] += 1  
              
            s = 0  
            for h in range(n,0, -1):  
                s += equal_h[h]  
                if s>=h:  
                    return h  
                  
            return 0
    

    And O(nlogn)

    class Solution(object):  
        def hIndex(self, citations):  
            citations.sort(reverse=True)  
            return max([min(k+1, v) for k,v in enumerate(citations)]) if citations else 0

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.