215. 数组中的第K个最大元素
Difficulty: 中等
在未排序的数组中找到第 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 ≤ 数组的长度。
Solution
快速排序解法一：在快速排序的partition过程中，可以确定的是切分点pivot的位置在最终的排序结果中不会变化，如果是降序排列，那么切分点左边的数都大于等于切分点位置的数，切分点右边的数都小于等于切分点位置的数。题目要求给出数组第k个最大的数，在降序排列的过程中，如果切分点刚好等于k-1，就能直接返回结果，如果切分点在k-1的左侧则去切分点的左侧[left,p-1]去寻找，否则去右侧[p+1,right]。
- 时间复杂度：
O(n)，如上文所述，证明过程可以参考「《算法导论》9.2：期望为线性的选择算法」 - 空间复杂度：
O(1)
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
if not nums or not k:
return None
left, right = 0, len(nums)-1
while 1:
p = self.partition(nums, left, right)
if p == k-1:
return nums[p]
elif p > k-1:
right = p - 1
else:
left = p + 1
def partition(self, arr, low, high):
i = low - 1
pivot = arr[high]
for j in range(low, high):
if arr[j] >= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1]
return i+1
快速排序解法二：直接应用快速排序将整个数组排序，然后返回-k索引位置的数字
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
if not nums or not k:
return None
left, right = 0, len(nums)-1
self.qSort(nums, left, right)
return nums[-k]
def qSort(self, arr, low, high):
if len(arr) <= 1:
return arr
if low < high:
p = self.partition(arr, low, high)
self.qSort(arr, low, p-1)
self.qSort(arr, p+1, high)
def partition(self, arr, low, high):
i = low - 1
pivot = arr[high]
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1]
return i+1