1.题目基本信息

1.1.题目描述

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

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

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

1.2.题目地址

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

2.解题方法

2.1.解题思路

优先队列（这个很简单就不介绍了）（时间复杂度：O(nlog(n))） / 快速排序（时间复杂度：O(n)）

2.2.解题步骤

第一步，定义快排递归函数。递归任务：返回arr[left,...,right]中从小到大第relK个元素

1.1.构建递归退出条件

1.2.确定基准值pivot

1.3.双指针移动

1.4.递归调用

3.解题代码

Python代码

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # 思路：基于快速排序的选择
        # 第一步，定义快排递归函数。递归任务：返回arr[left,...,right]中从小到大第relK个元素
        def quickSort(arr:list[int], left:int, right:int, relK:int) -> int:
            # 1.1.递归退出条件
            if left >= right:
                return arr[left]
            # 1.2.确定基准值pivot
            pivot = arr[left]
            # 1.3.双指针移动
            l, r = left - 1, right + 1
            while l < r:
                l += 1
                r -= 1
                while arr[l] > pivot:
                    l += 1
                while arr[r] < pivot:
                    r -= 1
                if l < r:
                    arr[l], arr[r] = arr[r], arr[l]
            # print(arr, left, right, l, r, relK)
            # 1.4.递归调用
            if relK <= r - left + 1:
                return quickSort(arr, left, r, relK)
            else:
                return quickSort(arr, r + 1, right, relK - (r - left + 1))
        return quickSort(nums, 0, len(nums) - 1, k)

4.执行结果