LeetCode 215. 数组中的第 K 个最大元素
这道题目其实非常的简单，使用 C++ 的 priority_queue 就可以模拟堆来快速的解题。但是今天我要汇总的两种做法需要自己重新造轮子，而不是使用现成的排序算法以及堆的数据结构。
题目描述
给定一个数组以及一个 k 值，返回数组中第 k 大元素。
输入输出样例
输入：nums = [3, 2, 1, 5, 6, 4]; k = 2
输出：5
思路
下面我将总结两种可以解决这道题目的思路。
思路一：快速选择
第一种解法是基于快速排序的，但是可以在手搓的快排算法基础上进行一些优化。
快速排序算法说穿了就是基于分治自顶向下地对一个序列进行排序，首先选择一个 pivot 作为哨兵节点，然后每一趟排序都要使 pivot 左侧的序列中所有值都比 pivot 要小，pivot 右侧的所有值比 pivot 要大。
在此基础上，我们不再分治地对两个子序列进行排序，而是寻找第 k 大的元素在哪一个序列当中，对这个序列进行排序即可。
思路二：堆排序
堆排序其实是将一个序列转换为一个完全二叉树，假设我们想构建一个大根堆，那么就需要从第一个非叶子结点开始，递归地将二叉树转换为堆，大根堆的特点是根节点（父节点）的值一定要大于子节点，因此每一次进行 heapify 操作时我们要做的就是比较父节点与两个子节点之间的关系，如果父节点的值不是最大的，那么就将子节点中的最大值与父节点交换，然后再递归地去对子节点进行 heapify 即可。
基于大根堆对数组进行堆排序之后，此时数组当中的第一个元素一定是整个数组中的最大值，但是尚不能保证整个数组是降序排序的，因为可能会出现二叉树中局部满足父节点的值大于子节点但数组非降序的情况出现。我们要找的是数组中第 k 大的元素，一个可行的做法就是将最后一个元素与最大的元素换个位置，然后将数组的长度减一，再次进行堆排，如此反复，不断地删除堆排序之后数组头部的元素，就可以找到第 k 大的元素。
C++ 代码
思路一：快速选择
class Solution {
public:int quickSelect(vector<int> &nums, int l, int r, int k) {if(l >= r) {return nums[k];}int pivot = nums[l];int i = l - 1, j = r + 1;while(i < j) {do i ++; while(pivot > nums[i]);do j --; while(pivot < nums[j]);if(i < j) {swap(nums[i], nums[j]);}}if(k <= j) return quickSelect(nums, l, j, k);else return quickSelect(nums, j+1, r, k);}int findKthLargest(vector<int>& nums, int k) {return quickSelect(nums, 0, nums.size() - 1, nums.size() - k);}
};
思路二：堆排序
class Solution {
public:void maxHeapify(vector<int> &nums, int i, int heapSize) {int l = i * 2 + 1, r = i * 2 + 2;int largest = i;if(l < heapSize && nums[largest] < nums[l]) {largest = l;}if(r < heapSize && nums[largest] < nums[r]) {largest = r;}if(i != largest) {swap(nums[i], nums[largest]);maxHeapify(nums, largest, heapSize);}}void buildHeap(vector<int> &nums, int heapSize) {for(int i=heapSize/2-1; i>=0; i--) {maxHeapify(nums, i, heapSize);}}int findKthLargest(vector<int>& nums, int k) {int heapSize = nums.size();buildHeap(nums, heapSize);int n = nums.size();for(int i=n-1; i>=n-k+1; i--) {swap(nums[0], nums[i]);heapSize --;maxHeapify(nums, 0, heapSize);}return nums[0];}
};
 - Block Parser)
