数组中的第K大的数字

问题简述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

详细描述

给定整数数组 nums 和整数 k，请返回数组中第 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

提示：
    1 <= k <= nums.length <= 10^4
    -10^4 <= nums[i] <= 10^4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/xx4gT2
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

思路1：partition操作（分治）

• partition操作描述：先随机确定一个锚点，然后将数组划分为小于锚点和大于锚点的两部分呢；

import random


class Solution:
    """"""

    def findKthLargest(self, nums: List[int], k: int) -> int:  # noqa
        """"""
        lo, hi = 0, len(nums) - 1

        while True:  # 第 k 大，排序后期下标应该是 k - 1
            idx = self.partition(nums, lo, hi)
            if idx + 1 == k:
                return nums[idx]
            elif idx + 1 < k:
                lo = idx + 1
            else:
                hi = idx - 1

    def partition(self, nums: List[int], lo: int, hi: int) -> int:
        """"""
        # === 挑选锚点 ===
        # 方式1）默认选 lo 作为锚点
        # pivot = nums[lo]

        # 方式2）随机选择一个锚点，并把锚点固定到首位或末位，这里交换到首位
        flag = random.randint(lo, hi)
        pivot = nums[flag]
        nums[flag], nums[lo] = nums[lo], nums[flag]

        # === partition 操作 ===
        # 方式1）单向遍历
        idx = lo  # 记录锚点在数组中的升序顺位
        for i in range(lo + 1, hi + 1):
            if nums[i] > pivot:  # 找到一个大于锚点的值
                idx += 1
                nums[idx], nums[i] = nums[i], nums[idx]

        nums[idx], nums[lo] = nums[lo], nums[idx]  # 把锚点交换到 idx 的位置

        return idx

        # 方式2）左右交换
        # l, r = lo, hi
        # while l < r:
        #     while l < r and nums[r] <= pivot:
        #         r -= 1
        #     while l < r and nums[l] >= pivot:
        #         l += 1
        #     if l < r:
        #         nums[l], nums[r] = nums[r], nums[l]
        # nums[lo], nums[l] = nums[l], nums[lo]
        #
        # return l

思路2：大顶堆（Python，调库）

import heapq


class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        """"""
        heap = []
        
        for x in nums:
            heapq.heappush(heap, -x)  # 默认是小顶堆，这里传入 -x，模拟大顶堆
            
        for _ in range(k - 1):
            heapq.heappop(heap)
            
        return -heap[0]