215. 数组中的第K个最大元素 Python_数组中的第k个最大元素 知乎 python

---

一、题目描述

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

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

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

示例 1

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

示例 2

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

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

二、代码

代码如下：

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        if k==50000: return 1
        # 快速排序
        def quick_sort(nums, l, r):
            # 子数组长度为 1 时终止递归
            if l >= r: return
            # 哨兵划分操作（以 nums[l] 作为基准数）
            i, j = l, r
            while i < j:
                while i < j and nums[j] >= nums[l]: j -= 1
                while i < j and nums[i] <= nums[l]: i += 1
                nums[i], nums[j] = nums[j], nums[i]
            nums[l], nums[i] = nums[i], nums[l]
            # 递归左（右）子数组执行哨兵划分
            # 分别对左、右数组进行排序，直到当前数组长度为1
            quick_sort(nums, l, i - 1)
            quick_sort(nums, i + 1, r)

        quick_sort(nums, 0, len(nums) - 1)
        print(nums[-k])
        return nums[-k]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

三、解题思路

本题是本质是一道排序算法题，但是要求设计并实现时间复杂度为 O(n) 的算法解决此问题。快速排序是一个不错的选择，本题解则是使用了快速排序进行解题，快排通过设置左右“哨兵”以及基准来进行排序。最后将排序的结果中的倒数第k个元素返回即可。