leetcode 215

题目描述

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

样例

示例 1: 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 示例 2: 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4 说明: 你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

---

算法1

(库函数排序) $O(nlong(n)$

对于这一道题，最直观的做法便是使用内置的排序函数排序，而第k大就是从小到大排第n-k+1个元素,他的下标则是n-k

C++ 代码

class Solution { public: int findKthLargest(vector<int>& nums, int k) { sort(nums.begin(),nums.end()); return nums[nums.size()-k]; } };

算法二

堆排序（nlong(n)）

对于第k个元素，也可以使用堆排序来做，c++内置了优先队列，是一个小根堆，他的堆顶是最大的元素，有两种写法

1 将所有元素入堆，弹出k-1个元素，剩下的堆中的堆顶就是第k大，2 一个一个入堆，如果堆容量超过n-k,就入堆一个，再弹出一个，维护一个k大小的堆，最后堆顶便是第k大 写法1 class Solution { public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int> q; for(int i=0;i<nums.size();i++){ q.push(nums[i]); if(q.size()>(nums.size()-k+1)) q.pop(); } return q.top(); } };

写法2

class Solution { public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int> q; for(int i=0;i<nums.size();i++){ q.push(nums[i]); if(q.size()>(nums.size()-k+1)) q.pop(); } return q.top(); } };

算法三

快速选择O（n）

算法一内置的sort底层实现也是一种快速排序算法，类似于快速排序的思想，在每次完成一次划分之后，可以判断要寻找的第k大的数也就是数组坐标k-1的与每次的划分点j分界线的大小，由于每趟快排分界点的数都放在了最终排序后的位置，当[k-1]小于等于j时，此时要寻找的第k大的数字位于j前面的区域，根据二分的思想，可以得知k必定不在j之后的区域，因此只对前面部分排序，反之则直对后面部分排序，弱l=r说明只有一个元素，便是我们要找的k大的值 时间复杂度分析：O(n) 第一次扫描一遍n次，第二趟平均n/2次，第k次平均n/(2^k)次，这一级数和收敛，因此时间复杂度还是O(n)

class Solution { public: int findKthLargest(vector<int>& nums, int k) { int n=nums.size(); return partition(nums,0,n-1,k); } int partition(vector<int>& nums,int l,int r,int k){ if(l==r) return nums[r]; int i=l-1,j=r+1,x=nums[l]; while(i<j){ do i++;while(nums[i]>x); do j--;while(nums[j]<x); if(i<j) swap(nums[i],nums[j]); else break; } if(j>=k-1) return partition(nums,l,j,k);//因为第k大对应下标为k-1 else return partition(nums,j+1,r,k); // return 0; } };