数组中的第K个最大元素

中英题面

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

Find thekth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

示例 1:

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

For example,
Given[3,2,1,5,6,4]and k = 2, return 5.

示例2:

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

说明:

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

Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.

算法

利用快速排序的思想查找第K大数。

平均时间复杂度：

O(N)

最坏时间复杂度：

O(N²)

平均空间复杂度：

O(N)

最坏空间复杂度：

O(N²)

代码

1 class Solution:
 2     def findKthLargest(self, nums, k):
 3         """
 4         :type nums: List[int]
 5         :type k: int
 6         :rtype: int
 7         """
 8         hen = 0
 9         tai = len(nums) - 1
10         mid = nums[tai // 2]
11         while (hen <= tai):
12             while (nums[hen] > mid):
13                 hen += 1
14             while (nums[tai] < mid):
15                 tai -= 1
16             if (hen <= tai):
17                 nums[hen], nums[tai] = nums[tai], nums[hen]
18                 hen += 1
19                 tai -= 1
20         if (k - 1 <= tai):
21             return self.findKthLargest(nums[: tai + 1], k)
22         if (k - 1 >= hen):
23             return self.findKthLargest(nums[hen :], k - hen)
24         return nums[k - 1]