题目：数组中的第K个最大元素
- 在未排序的数组中找到第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 ≤ 数组的长度。
来源：力扣（LeetCode）第215题
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
分析：
- 有两种做法，一种是使用快排思想，选中一个数，对其进行
partition。 - 第二种做法是使用堆，维护一个大顶堆，要拿到第k大元素就删除堆顶k次
代码：
快速排序改进：
class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: self.k = k ans = self.quickSort(nums, 0, len(nums) - 1) return ans if ans else nums[k-1] def portition(self, arr, start, end): pivot = arr[end] i = start - 1 for j in range(start, end): if pivot < arr[j]: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i+1], arr[end] = arr[end], arr[i+1] return i + 1 def quickSort(self, arr, start, end): if start < end: pivot = self.portition(arr, start, end) if pivot + 1 == self.k: # 唯一与快排的区别就是当pivot已经是第k大元素时就直接返回。 return arr[pivot] self.quickSort(arr, start, pivot - 1) self.quickSort(arr, pivot + 1, end)使用堆：
class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: self.length = len(nums) for i in range(self.length // 2 - 1, -1, -1): # 把数组构建成堆 self.maxheapify(nums, i) ans = nums[0] for i in range(k): # 拿到第k大元素 ans = nums[0] nums[0] = nums[self.length - 1] self.length -= 1 self.maxheapify(nums, 0) return ans def maxheapify(self, heap, i): # 堆的关键方法，作用是维护堆，任何涉及到堆的操作基本都需要。 left = 2 * (i + 1) - 1 right = 2 * (i + 1) largest = i if left < self.length and heap[largest] < heap[left]: largest = left if right < self.length and heap[largest] < heap[right]: largest = right if largest != i: heap[largest], heap[i] = heap[i], heap[largest] self.maxheapify(heap, largest)
复杂度分析：
- 快速排序：
- 时间复杂度：O(nlogn)这是最坏情况下，最好情况下为O(n)
- 空间复杂度：O(1) 快速排序本来就是原地排序，不需要额外的空间。
- 使用堆：
- 时间复杂度：O(nlogn) n为二分之一的数组长度，
maxheapify的时间复杂度为logn - 空间复杂度：O(1) 构建堆以及拿出堆顶都只需要常数空间。
- 时间复杂度：O(nlogn) n为二分之一的数组长度，