[LeetCode]215. 数组中的第K个最大元素(Kth Largest Element in an Array)

题目描述

在未排序的数组中找到第 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 ≤ 数组的长度。

解题思路

使用快排的思想,但不完全排序,只对其中一半进行循环排序。具体地,找一个中间数,大于该数的数字放到左边,小于的放到右边,之后判断该数所在的位置,若下标等于k,则输出该数,若小于k,则说明目标数字在其右边,若大于k,则说明在其左边,再递归即可。

代码

Python 3.6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
start, end = 0, len(nums)
while end > start:
mid, nums = self.split_list(nums, start, end)
if mid == k - 1:
return nums[mid]
elif mid > k - 1:
end = mid
else:
start = mid + 1

def split_list(self, nums, start, end):
left, right = [], []
cur = nums[start:end][0]
for i in nums[start:end]:
if i > cur:
left.append(i)
else:
right.append(i)
return start + len(left), nums[:start] + left + right + nums[end:]

执行用时:3344 ms
内存消耗:13.4 MB