Two python solutions


  • 0
    Y

    One O(n) time and O(n) space:

        def hIndex(self, citations):
            """
            :type citations: List[int]
            :rtype: int
            """
            nc = len(citations)
            citCounts = (nc+1)*[0]
            for n in citations:
                if n>=nc:
                    citCounts[nc] += 1
                else:
                    citCounts[n] += 1
            accumC=0
            for i in range(nc,-1,-1):
                accumC += citCounts[i]
                if accumC>=i:
                    return i
            return i
    

    One O(nlgn) time and O(1) space:

        def hIndex(self, citations):
            """
            :type citations: List[int]
            :rtype: int
            """
            def onePartition(loc,citations,s,e):
                pivot = citations[loc]
                index = s
                for i in range(s,e):
                    cit = citations[i]
                    if cit>=pivot:
                        citations[i] = citations[index]
                        citations[index] = cit
                        index += 1
                citations[loc] = citations[index-1]
                citations[index-1] = pivot
                return index-1
                        
            nc = len(citations)
            if not nc: return 0
            loc,s,e = 0,1,nc
            hindex = 1 if citations[loc]>0 else 0
            while(s<=e):
                #print 'Before: ',loc,' ',citations
                nloc = onePartition(loc,citations,s,e)
                if(nloc+1==citations[nloc]):
                        return max(hindex,nloc+1)
                elif(nloc+1>citations[nloc]):
                    hindex = max(hindex,citations[nloc])
                    loc,s,e=loc,s,nloc
                else:
                    hindex = max(hindex,nloc+1)
                    loc,s,e=nloc+1,nloc+2,e
                #print 'After: ', nloc,' ',citations,' ',hindex
            return hindex
    

Log in to reply
 

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