90 数组中的第K个最大元素

组中的第K个最大元素"/>

90 数组中的第K个最大元素

数组中的第K个最大元素

• • 题解1 最小堆（STL实现）
  • 题解2 快排的partition思想
  • 题解3 手撸大根堆(记忆+理解)
  • • 参考link：

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

你必须设计并实现时间复杂度为 O ( n ) O(n) 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 <= 1 0 5 10^5 105
• − 1 0 4 -10^4 −104 <= nums[i] <= 1 0 4 10^4 104

题解1 最小堆（STL实现）

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {// 小根堆priority_queue<int, vector<int>, greater<int>> q;for(auto& i : nums){q.push(i);if(q.size() > k)q.pop();}return q.top();}
};

题解2 快排的partition思想

class Solution {
public:int quickSelect(vector<int>& nums, int l, int r, int k){if(l == r)return nums[k];int partition = nums[l];// 防止死循环int i = l-1;int j = r+1;while(i < j){do i++; while(nums[i] < partition);do j--; while(nums[j] > partition);if(i < j)swap(nums[i], nums[j]);}// 要找的下标比j小说明此时选择的在第k个数的右侧，递归左区间if(k <= j) return quickSelect(nums, l, j, k);// 否则递归右区间else return quickSelect(nums, j+1, r, k);}int findKthLargest(vector<int>& nums, int k) {int s = nums.size();return quickSelect(nums, 0, s-1, s-k);}
};

题解3 手撸大根堆(记忆+理解)

大根堆就是根节点是整棵树的最大值(根节点大于等于左右子树的最大值)，对于他的任意子树，根节点也是最大值。

参考link：

1. java版本
2. C++版本

class Solution 
{
public:int findKthLargest(vector<int>& nums, int k) {int n = nums.size();// 先按层序构建堆的二叉树形build_maxHeap(nums);for (int i = 0; i < k - 1; i ++){// 0 <-> n-1// 0 <-> n-2//  ···// 把每个数都换到头上试试swap(nums[0], nums[n-1-i]);// n - 2、n - 3 ... （视为依次插入元素）adjust_down(nums, 0, n-1-i - 1);}return nums[0];}void build_maxHeap(vector<int> & nums){// 构建过程：/**1. 设数组中从0到i-1位置的元素是一个大根堆, 把第i个位置的元素插入大根堆里2. 为了符合大根堆的定义， 需要从第i个位置的元素开始，依次看它的父节点的值是否小于它3. 如果小于就进行交换，直到它的父节点不小于它，或者到了该大根堆的最顶端的根节点，这一次过程才算彻底结束**/int n = nums.size();// 找到二叉树最后一个非叶子结点for (int root = n/2; root > -1; root --)adjust_down(nums, root, n - 1);}void adjust_down(vector<int> & nums, int root, int hi){if (root > hi)return ;// 先记录下int t = nums[root];// 左孩子indiceint child = 2 * root + 1;while (child <= hi){// 看最大的是不是右孩子if (child + 1 <= hi && nums[child] < nums[child + 1])child ++;// 不需要变动（父节点>子节点）if (t > nums[child])break;// 换，这里可以写swap函数nums[root] = nums[child];root = child;// 继续换child = 2 * root + 1;}nums[root] = t;}
};