LeetCode-215.数组中的第K个最大元素

. - 力扣（LeetCode）给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

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

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

• 1 <= k <= nums.length <= 105
• -104 <= nums[i] <= 104

思路1：基于堆排序的选择方法

排序 - - - 选择排序（简单选择、堆排序）_c#排序中选择排序中的dui排序-CSDN博客

「调整」

        父节点都大于或小于子结点

// 以root为根，调整大根堆void heapAdjust(vector<int>& nums, int root, int heapSize){int i = root;  // i保存根节点下标for(int j = i*2 + 1; j < heapSize; j = i*2+1){// j保存孩子中最大值下标if(j < heapSize - 1 && nums[j] < nums[j+1]){j++;}if(nums[i] >= nums[j]){break;}else{swap(nums[i], nums[j]);i = j;}}}

「建堆」

        将排序码k1，k2，k3，…，kn表示成一棵完全二叉树，然后从第 n/2个排序码(即树的最后一个非终端结点)开始筛选，使由该结点作根结点组成的子二叉树符合堆的定义，然后从第 n/2-1 个排序码重复刚才操作，直到第一个排序码止。

void buildHeap(vector<int>&nums, int heapSize){for(int i = heapSize / 2; i >= 0; i--){heapAdjust(nums, i, heapSize);}}

「删除」

        将堆中第一个结点（二叉树根结点）和最后一个结点的数据进行交换（k1与kn），再将k1~kn-1重新建堆，然后k1和kn-1交换，再将k1~kn-2重新建堆，然后k1和kn-2交换，如此重复下去，每次重新建堆的元素个数不断减1，直到重新建堆的元素个数仅剩一个为止。这时堆排序已经完成，则排序码k1，k2，k3，…，kn已排成一个有序序列。

class Solution {
private:// 以root为根，调整大根堆void heapAdjust(vector<int>& nums, int root, int heapSize){int i = root;  // i保存根节点下标for(int j = i*2 + 1; j < heapSize; j = i*2+1){// j保存孩子中最大值下标if(j < heapSize - 1 && nums[j] < nums[j+1]){j++;}if(nums[i] >= nums[j]){break; // 因为从叶子节点向上调节，所以没有节点交换，其子树也不许变化}else{swap(nums[i], nums[j]);i = j; // j节点调整，其子树也需要调整}}}void buildHeap(vector<int>&nums, int heapSize){for(int i = heapSize / 2; i >= 0; i--){heapAdjust(nums, i, heapSize);}}public:int findKthLargest(vector<int>& nums, int k) {int heapSize = nums.size();buildHeap(nums, heapSize);// 第k大数倒数for(int i = nums.size() - 1; i > nums.size() - k; --i){swap(nums[0],nums[i]);--heapSize;heapAdjust(nums, 0, heapSize);}return nums[0];}
};

思路2：基于快速排序的选择方法

排序 - - - 交换排序（快速排序、冒泡排序）-CSDN博客

class Solution {
private:int partition(vector<int>&nums, int l, int r){int key = nums[l];while(l < r){while(l < r && nums[r] >= key) r--;nums[l] = nums[r];while(l < r && nums[l] <= key) l++;nums[r] = nums[l];}nums[l] = key;return l;}int quickSelect(vector<int>& nums, int l, int r, int k){int index = partition(nums, l, r);if(index == k)return nums[k];elsereturn index < k ? quickSelect(nums, index + 1, r, k)  // index数小于第k数则在index右边查找: quickSelect(nums, l, index - 1, k); // index数大于第k数则在index左边查找}public:int findKthLargest(vector<int>& nums, int k) {return quickSelect(nums, 0, nums.size() - 1, nums.size() - k); // 返回倒数k位置数}
};