古典风格中药医药企业网站模板源码,wordpress 产品展示 插件,桃城网站建设公司,加盟. - 力扣#xff08;LeetCode#xff09;给定整数数组 nums 和整数 k#xff0c;请返回数组中第 k 个最大的元素。
请注意#xff0c;你需要找的是数组排序后的第 k 个最大的元素#xff0c;而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问…. - 力扣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(vectorint nums, int root, int heapSize){int i root; // i保存根节点下标for(int j i*2 1; j heapSize; j i*21){// j保存孩子中最大值下标if(j heapSize - 1 nums[j] nums[j1]){j;}if(nums[i] nums[j]){break;}else{swap(nums[i], nums[j]);i j;}}}
「建堆」 将排序码k1k2k3…kn表示成一棵完全二叉树然后从第 n/2个排序码(即树的最后一个非终端结点)开始筛选使由该结点作根结点组成的子二叉树符合堆的定义然后从第 n/2-1 个排序码重复刚才操作直到第一个排序码止。
void buildHeap(vectorintnums, 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直到重新建堆的元素个数仅剩一个为止。这时堆排序已经完成则排序码k1k2k3…kn已排成一个有序序列。
class Solution {
private:// 以root为根调整大根堆void heapAdjust(vectorint nums, int root, int heapSize){int i root; // i保存根节点下标for(int j i*2 1; j heapSize; j i*21){// j保存孩子中最大值下标if(j heapSize - 1 nums[j] nums[j1]){j;}if(nums[i] nums[j]){break; // 因为从叶子节点向上调节所以没有节点交换其子树也不许变化}else{swap(nums[i], nums[j]);i j; // j节点调整其子树也需要调整}}}void buildHeap(vectorintnums, int heapSize){for(int i heapSize / 2; i 0; i--){heapAdjust(nums, i, heapSize);}}public:int findKthLargest(vectorint 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(vectorintnums, 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(vectorint 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(vectorint nums, int k) {return quickSelect(nums, 0, nums.size() - 1, nums.size() - k); // 返回倒数k位置数}
};
