Two best algorithm to get kth-max number without built-in function


  • 0
    E

    Algorithm 1:partition (quick sort's) + binary search

    def findKthLargest(self, nums, k):
        target,st,en=-1,0,len(nums)-1
        while len(nums)-target!=k:
            if target>-1: #binary search
                if len(nums)-target>k:st=target+1
                else:en=target-1
            j,i,target=st-1,st,en
            while i<en: #partition
                if nums[i]<nums[target]:j+=1;nums[j],nums[i]=nums[i],nums[j]
                i+=1
            j+=1;nums[j],nums[target]=nums[target],nums[j]
            target=j
        return nums[target]
    

    Tn=O(nlgn)
    Pn=O(1)

    Algorithm 2:k-min-priority-heap

    def findKthLargest(self, nums, k):
        self.make_min_heap(nums,k) #create heap
        for n in nums[k:]:
            if n>nums[0]:n,nums[0]=nums[0],n;self.modify(nums,k,0) #modify top of heap
        return nums[0]
    
    def modify(self,nums,k,i):
        m=i
        if 2*i+1<k and nums[m]>nums[2*i+1]:m=2*i+1
        if 2*i+2<k and nums[m]>nums[2*i+2]:m=2*i+2
        if m!=i:
            nums[m],nums[i]=nums[i],nums[m]
            if m<=(k-2)/2:self.modify(nums,k,m)
    
    def make_min_heap(self,nums,k):
        for i in range((k-2)/2,-1,-1):self.modify(nums,k,i)
    

    Tn=O(nlgn) but this is more effective than algorithm 1
    Pn=O(k)


Log in to reply
 

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