LeetCode 215. 数组中的第K个最大元素（快排、堆排的应用。遇到海量数据时如何处理？）

tech2022-08-08 117

2020年9月2日周三天气晴【不悲叹过去，不荒废现在，不惧怕未来】

本文目录

题目简介1. 基于快排的快速选择（quick select）方法（减治）1.1 递归版本1.2 迭代版本 2. 最小堆（第k大）/ 最大堆（第k小）3. 红黑树参考文献

题目简介

215. 数组中的第K个最大元素雷同题目：剑指offer 40. 最小的k个数(经典TopK问题)

1. 基于快排的快速选择（quick select）方法（减治）

1.1 递归版本

class Solution { public: int findKthLargest(vector<int>& nums, int k) { int len = nums.size(); // 设置随机数种子 srand(time(0)); // 第k大，所以升序排列是第 len-k 个元素 return quickSelect(nums,0,len-1,len-k); } // 基于快排的选择方法（quick select） int quickSelect(vector<int>& nums, int l, int r, int k){ int rand_idx = rand() % (r-l+1) + l; swap(nums[l],nums[rand_idx]); int idx = partition(nums,l,r); if(idx==k) return nums[idx]; else return idx<k?quickSelect(nums,idx+1,r,k):quickSelect(nums,l,idx-1,k); } // 分割操作（以中轴元素为基准，将数组分割成三部分，返回中轴元素索引） int partition(vector<int>& nums, int l, int r){ int pivot = nums[l]; // 取第一个位置的元素作为中轴元素 // 右边主动接近左边，进行循环覆盖 while(l < r){ // 从右边寻找第一个大于 pivot 的数 while(l < r && nums[r] > pivot) --r; // 找到后直接进行覆盖 nums[l] = nums[r]; // 从左边寻找第一个小于等于 pivot 的数 while(l < r && nums[l] <= pivot) ++l; // 找到后直接进行覆盖 nums[r] = nums[l]; } // 把pivot交换到中间，完成分割 nums[l] = pivot; return l; } }; 时间复杂度：由于引入了随机化，时间代价的期望是

O\left( {n} \right)

空间复杂度：递归调用的期望深度为

O\left( {logn} \right)

1.2 迭代版本

class Solution { public: int findKthLargest(vector<int>& nums, int k) { // 设置随机数种子 srand(time(0)); int len = nums.size(); int target = len - k; int left = 0; int right = len - 1; while (true) { int index = partition(nums, left, right); if (index < target) { left = index + 1; } else if (index > target) { right = index - 1; } else { return nums[index]; } } } // 分割操作（以中轴元素为基准，将数组分割成三部分，返回中轴元素索引） int partition(vector<int>& nums, int l, int r){ int rand_idx = rand() % (r-l+1) + l; swap(nums[l],nums[rand_idx]); int pivot = nums[l]; // 取第一个位置的元素作为中轴元素 // 右边主动接近左边，进行循环覆盖 while(l < r){ // 从右边寻找第一个大于 pivot 的数 while(l < r && nums[r] > pivot) --r; // 找到后直接进行覆盖 nums[l] = nums[r]; // 从左边寻找第一个小于等于 pivot 的数 while(l < r && nums[l] <= pivot) ++l; // 找到后直接进行覆盖 nums[r] = nums[l]; } // 把pivot交换到中间，完成分割 nums[l] = pivot; return l; } }; 时间复杂度：由于引入了随机化，时间代价的期望是

O\left( {n} \right)

空间复杂度：递归改为了迭代，时间复杂度位

O\left( {1} \right)

另外很重要的一点就是，partition()分割函数用循环覆盖的方法实现的话，虽然很巧妙，但是比较难想，特别是在面试时需要手撕代码的时候，很容易一紧张就忘了，所以下面给出常规思路：把小于 pivot 的元素都交换到前面，最后再把 pivot 的值交换到中间。具体代码如下：

class Solution { public: int findKthLargest(vector<int>& nums, int k) { // 设置随机数种子 srand(time(0)); int len = nums.size(); int target = len - k; int l = 0, r = len - 1; while(true){ int idx = partition(nums,l,r); if(idx==target) break; else if(idx>target) r = idx - 1; else l = idx + 1; } return nums[target]; } // 分割操作常规思路（以中轴元素为基准，将数组分割成三部分，返回中轴元素索引） int partition(vector<int>& nums, int l, int r){ int rand_idx = rand()%(r-l+1)+l; swap(nums[l], nums[rand_idx]); int pivot = nums[l]; // j 的初始位置为 l，并且在循环的过程中，始终保持 nums[j] <= pivot int j = l; for(int i=l+1;i<=r;++i){ // 小于 pivot 的元素都被交换到前面 if(nums[i]<pivot){ ++j; swap(nums[i],nums[j]); } } swap(nums[l],nums[j]); return j; } };

2. 最小堆（第k大）/ 最大堆（第k小）

本题也可以用最小堆：根据数组前 k 个元素建立一个大小为 k 的最小堆，然后遍历剩下的数组元素，与堆顶元素进行比较，动态调整堆中的元素，数组遍历结束后的堆中元素就是数组中前 k 大的元素，堆顶元素是堆中最小元素，也就是第 k 大的元素。

class Solution { public: int findKthLargest(vector<int>& nums, int k) { // 复制数组前k个元素到堆中 vector<int> minHeap(nums.begin(), nums.begin()+k); // 调整为最小堆 for(int i=k/2-1;i>=0;--i){ minHeapAdjustDown(minHeap,i,k); } // 从第k+1个元素开始遍历数组，将数组元素与堆顶元素进行比较 for(int i=k;i<nums.size();++i){ // 大于堆顶元素，则替换之 if(nums[i]>minHeap[0]){ swap(nums[i],minHeap[0]); minHeapAdjustDown(minHeap,0,k); } } // 遍历结束后，堆顶元素即为第k大元素 return minHeap[0]; } // 最小堆向下调整（常用于删除元素） void minHeapAdjustDown(vector<int>& minHeap, int parent, int len) { int child = 2 * parent + 1; int num = minHeap[parent]; while (child < len) { if (child + 1 < len && minHeap[child + 1] < minHeap[child]) ++child; if (num > minHeap[child]) { minHeap[parent] = minHeap[child]; parent = child; child = 2 * parent + 1; } else break; } minHeap[parent] = num; } };

也可以用STL中的优先队列priority_queue 来实现，这里就不详细写了。

3. 红黑树

借助STL中的mutilset来实现，过程和使用priority_queue 实现很像，这里也不详细写了。另外，虽然第二种方法时间复杂度更高，但是更适合用于海量数据，所以这两种方法各有优劣，海量数据的TopK问题可以参考这篇文章：【面试现场】如何在10亿数中找出前1000大的数。

参考文献

https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcode-/

最新回复(0)