Kth Largest Element

标签：right nums int hq pos Element Kth Largest left

https://leetcode.cn/problems/kth-largest-element-in-an-array/  

 

solution1:

使用min-heap，找第k大的元素

 

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # python默认是小顶堆
        hq = nums[:k]
        heapq.heapify(hq)
        for i in range(k, len(nums)):
            if nums[i] > hq[0]:
                heapq.heappop(hq)
                heapq.heappush(hq, nums[i])
        
        return hq[0]

View Code

 

solution2:

import random
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def partition(nums, left, right):
            # 1.generating a random number between the starting index of the array 
            # and the ending index of the array
            p = random.randint(left, right)

            
            # 2.swapping ending element of the array and the pivot
            nums[p], nums[right] = nums[right], nums[p]
            pivot = nums[right]
            
            # 3. [0...pos) 存储小于pivot的元素
            pos = left
            for i in range(left, right):
                if nums[i] < pivot:
                    nums[pos], nums[i] = nums[i], nums[pos]
                    pos += 1
            nums[right], nums[pos] = nums[pos], nums[right]
            return pos 
        
        n = len(nums)
        left, right = 0, n - 1
        while left <= right:
            pos = partition(nums, left, right)
            if pos == n - k:
                break
            elif pos < n - k:
                left = pos + 1
            else:
                right = pos - 1
        return nums[pos]

View Code

 

标签：right,nums,int,hq,pos,Element,Kth,Largest,left
From： https://www.cnblogs.com/zijidan/p/16882827.html