215-kth-largest-element-in-an-array.md

215. 数组中的第K个最大元素 - medium

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

thinking

1. 库函数排序

排序，取倒数 k 个元素

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return sorted(nums)[-k]

2. 快排 + 选择

使用快速排序，每次只考虑 k 所在的那一组数据。

快排使用随机 p 值，效率高很多。

code

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        l, h = 0, len(nums) - 1
        m = len(nums)
        k = m - k
        while m != k:
            if m < k:
                l = m+1
            else:
                h = m-1
            m = self.quick_sort(nums, l, h)
        return nums[m]

    def quick_sort(self, nums: List[int], l: int, h: int) -> int:
        # 随机 p 值
        i = random.randint(l, h)
        nums[l], nums[i] = nums[i], nums[l]

        p = nums[l]

        while l < h:
            while nums[h] >= p and h > l:
                h -= 1
            nums[l] = nums[h]
 
            while nums[l] < p and l < h:
                l += 1
            nums[h] = nums[l]

        nums[l] = p
        return l