方法一快速选择算法最优解O (n) 时间复杂度这是唯一满足题目 O (n) 时间复杂度要求的解法也是面试首选。1. 核心思想基于快速排序的改进快速排序的核心是划分partition选一个元素作为主元pivot把数组分成两部分左边所有元素 ≤ 主元右边所有元素 ≥ 主元主元的最终位置就确定了不会再变快速选择的精髓是我们不需要把整个数组排序只需要找到目标位置的元素即可。我们要找的是第 k 大的元素也就是升序排序后下标为n-k的元素因为升序数组的倒数第 k 个就是第 n-k 个每次划分后看主元的位置 q 和目标位置n-k的关系如果q n-k主元就是我们要找的元素直接返回如果q n-k目标元素在右半部分递归右半区间如果q n-k目标元素在左半部分递归左半区间这样我们每次只需要递归一个区间而不是两个时间复杂度从快速排序的 O (nlogn) 降到了期望 O (n)。2. 完整解题步骤计算数组长度 n目标下标为target n - k调用快速选择函数在区间[0, n-1]中找下标为 target 的元素快速选择函数如果区间只有一个元素lr返回该元素对区间进行划分得到主元的位置 q根据 q 和 target 的关系递归左半或右半区间class Solution { public: int quickselect(vectorint nums,int l,int r,int k){ //参数1输入 //2左指针的初始位置 //3右指针的初始位置 //4从左往右数第k个 //左指针等于右指针 返回 if(l r){ return nums[k]; } //选择一个基准数 要求这个数的左边的值都小于他 右边的数都大于他 int p nums[l]; int i l-1;//出格 避免下面的循环不启动 int j r1; while(ij){ do i; while(nums[i]p);//要满足左边的数小于基准值循环结束的时候 i就是大于基准值的位置 do j--; while(nums[j]p);//右边的数要大于基准值循环结束j就是小于基准值的位置。 //小的需要在左边 大的在右边 //所以如果i在j左边 就得交换 if(ij){ swap(nums[i],nums[j]); } } //循环结束j的位置就是基准的位置 //接下来看看k目标位置和基准位置的关系 如果等于直接返回j。如果小于j就在左半部分 直接递归左半部分 反之亦然 if(k j ) return quickselect(nums,l,j,k); else return quickselect(nums,j1,r,k); } int findKthLargest(vectorint nums, int k) { int n nums.size(); //n-k是相当于升序后的倒数第K个 也就是第k个最大元素 return quickselect(nums,0,n-1,n-k); } };大根堆法大根堆 堆顶永远是整个堆里最大的数我们要找第 K 大思路超级简单把数组建成大根堆把最大的扔掉1 次把第二大的扔掉2 次……扔完 K-1 次以后堆顶就是第 K 大完美解决堆长啥样一句话堆就是一个数组但逻辑上是完全二叉树下标i的左孩子i*2 1下标i的右孩子i*2 2父节点永远比孩子大大根堆三、堆法只有 3 个核心动作1.调整堆heapify让一个位置重新变成大根堆把当前节点和左右孩子比谁大谁放上面不对就交换再递归调整。2.建堆从最后一个非叶子节点开始从下往上全部调整一遍。3.删除堆顶拿最大值堆顶和最后一个元素交换堆大小 -1重新调整堆顶class Solution { public: void heapify(vectorint a, int i, int size) { // 让i这个位置变成大根堆 int left i * 2 1; // 左孩子 int right i * 2 2; // 右孩子 int maxIdx i; // 先假设自己最大 // 如果左孩子或者右孩子更大 就最大值变成他 最后maxIdx存的就是最大值 // 左孩子更大 if (left size a[left] a[maxIdx]) maxIdx left; // 右孩子更大 if (right size a[right] a[maxIdx]) maxIdx right; // 如果最大的不是自己 那就交换 让自己是最大的 if (maxIdx ! i) { swap(a[i], a[maxIdx]); // 换完后调整 heapify(a, maxIdx, size); } } // 核心2建堆 → 把整个数组变成大根堆 void buildHeap(vectorint a, int size) { // 从最后一个非叶子节点往上建 for (int i size / 2 - 1; i 0; i--) { heapify(a, i, size); } } int findKthLargest(vectorint nums, int k) { int n nums.size(); // 建堆 buildHeap(nums, n); // 堆顶是最大数 int h n; // 把k-1次最大值弄出来 for (int i n - 1; i n - k 1; i--) { swap(nums[0], nums[i]); // 堆顶最大的数 放到最后 // 然后重新调整新堆顶 h--; heapify(nums, 0, h); } return nums[0]; } };
力扣100（38）堆-数组中的第K个最大元素
方法一快速选择算法最优解O (n) 时间复杂度这是唯一满足题目 O (n) 时间复杂度要求的解法也是面试首选。1. 核心思想基于快速排序的改进快速排序的核心是划分partition选一个元素作为主元pivot把数组分成两部分左边所有元素 ≤ 主元右边所有元素 ≥ 主元主元的最终位置就确定了不会再变快速选择的精髓是我们不需要把整个数组排序只需要找到目标位置的元素即可。我们要找的是第 k 大的元素也就是升序排序后下标为n-k的元素因为升序数组的倒数第 k 个就是第 n-k 个每次划分后看主元的位置 q 和目标位置n-k的关系如果q n-k主元就是我们要找的元素直接返回如果q n-k目标元素在右半部分递归右半区间如果q n-k目标元素在左半部分递归左半区间这样我们每次只需要递归一个区间而不是两个时间复杂度从快速排序的 O (nlogn) 降到了期望 O (n)。2. 完整解题步骤计算数组长度 n目标下标为target n - k调用快速选择函数在区间[0, n-1]中找下标为 target 的元素快速选择函数如果区间只有一个元素lr返回该元素对区间进行划分得到主元的位置 q根据 q 和 target 的关系递归左半或右半区间class Solution { public: int quickselect(vectorint nums,int l,int r,int k){ //参数1输入 //2左指针的初始位置 //3右指针的初始位置 //4从左往右数第k个 //左指针等于右指针 返回 if(l r){ return nums[k]; } //选择一个基准数 要求这个数的左边的值都小于他 右边的数都大于他 int p nums[l]; int i l-1;//出格 避免下面的循环不启动 int j r1; while(ij){ do i; while(nums[i]p);//要满足左边的数小于基准值循环结束的时候 i就是大于基准值的位置 do j--; while(nums[j]p);//右边的数要大于基准值循环结束j就是小于基准值的位置。 //小的需要在左边 大的在右边 //所以如果i在j左边 就得交换 if(ij){ swap(nums[i],nums[j]); } } //循环结束j的位置就是基准的位置 //接下来看看k目标位置和基准位置的关系 如果等于直接返回j。如果小于j就在左半部分 直接递归左半部分 反之亦然 if(k j ) return quickselect(nums,l,j,k); else return quickselect(nums,j1,r,k); } int findKthLargest(vectorint nums, int k) { int n nums.size(); //n-k是相当于升序后的倒数第K个 也就是第k个最大元素 return quickselect(nums,0,n-1,n-k); } };大根堆法大根堆 堆顶永远是整个堆里最大的数我们要找第 K 大思路超级简单把数组建成大根堆把最大的扔掉1 次把第二大的扔掉2 次……扔完 K-1 次以后堆顶就是第 K 大完美解决堆长啥样一句话堆就是一个数组但逻辑上是完全二叉树下标i的左孩子i*2 1下标i的右孩子i*2 2父节点永远比孩子大大根堆三、堆法只有 3 个核心动作1.调整堆heapify让一个位置重新变成大根堆把当前节点和左右孩子比谁大谁放上面不对就交换再递归调整。2.建堆从最后一个非叶子节点开始从下往上全部调整一遍。3.删除堆顶拿最大值堆顶和最后一个元素交换堆大小 -1重新调整堆顶class Solution { public: void heapify(vectorint a, int i, int size) { // 让i这个位置变成大根堆 int left i * 2 1; // 左孩子 int right i * 2 2; // 右孩子 int maxIdx i; // 先假设自己最大 // 如果左孩子或者右孩子更大 就最大值变成他 最后maxIdx存的就是最大值 // 左孩子更大 if (left size a[left] a[maxIdx]) maxIdx left; // 右孩子更大 if (right size a[right] a[maxIdx]) maxIdx right; // 如果最大的不是自己 那就交换 让自己是最大的 if (maxIdx ! i) { swap(a[i], a[maxIdx]); // 换完后调整 heapify(a, maxIdx, size); } } // 核心2建堆 → 把整个数组变成大根堆 void buildHeap(vectorint a, int size) { // 从最后一个非叶子节点往上建 for (int i size / 2 - 1; i 0; i--) { heapify(a, i, size); } } int findKthLargest(vectorint nums, int k) { int n nums.size(); // 建堆 buildHeap(nums, n); // 堆顶是最大数 int h n; // 把k-1次最大值弄出来 for (int i n - 1; i n - k 1; i--) { swap(nums[0], nums[i]); // 堆顶最大的数 放到最后 // 然后重新调整新堆顶 h--; heapify(nums, 0, h); } return nums[0]; } };
