题目描述
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.
题意:在一个无序数组中找到第k
大的数。
算法1
(分治)
题解1:分治。借用快速排序的思想,第k
大等于找第n - k + 1
小的数。这里我们以找第k
小为例,我们每次取区间头元素作为基准元素pivot
,然后将区间内所有小于这个数的数字都放在基准元素之前,所有大于这个数的数字都放在基准元素之后。如果基准元素左边的数字个数len
大于等于k
,那么我们就去左边区间找第k
小;如果基准元素恰好是第k
小的,那么返回基准元素;否则我们去右半区间找到第k - len - 1
小的元素。
//24ms
class Solution {
public:
int getKth(vector<int>&nums,int k,int l,int r)
{
if(l == r) return nums[l];
int pivot = nums[l],i = l , j = r;
while(i < j)
{
while(i < j && nums[j] >= pivot) j --;
while(i < j && nums[i] <= pivot) i ++;
if(i < j)
swap(nums[i],nums[j]);
}
swap(nums[i],nums[l]);
if(i - l >= k) return getKth(nums,k,l, i - 1);
else if(i - l + 1 == k) return nums[i];
else return getKth(nums,k - (i - l + 1),i + 1,r);
}
int findKthLargest(vector<int>& nums, int k) {
return getKth(nums, nums.size() - k + 1, 0 , nums.size() - 1);
}
};
当然了,c++提供了nth_element函数
,让我们把第k
大/小的元素(下标从0开始)放在对应的位置上,同时把小于该元素的元素都放在左边,大于该元素的元素都放在右边。
// 4ms
int findKthLargest(vector<int>& nums, int k) {
nth_element(nums.begin(),nums.begin() + k - 1, nums.end(),greater<int>());
return nums[k - 1];
}
算法2
(堆积排序) $O(nlogk)$
题解2:堆积排序,维护一个大小为k
的小顶堆,先将k
个元素入队,然后将剩下的元素和堆顶元素比较,如果大于堆顶元素,就弹出堆顶元素,并插入当前元素。堆中维护的始终是最大的k
个元素,堆顶元素就是第k
大了。
class Solution {
public:
vector<int> tree;
// 每次把堆顶元素和较小的左右子孩子交换,直至左右孩子都大于等于`temp`
void adjust(int root,int k)
{
int temp = tree[root];
int j = 2 * root + 1;
while(j < k)
{
if(j + 1 < k && tree[j + 1] < tree[j])
j ++;
if(temp < tree[j])
break;
tree[(j - 1) / 2] = tree[j];
j = j * 2 + 1;
}
tree[(j - 1) / 2] = temp;
}
int findKthLargest(vector<int>& nums, int k) {
tree = vector<int>(k);
int n = nums.size();
for(int i = 0 ; i < k ; i ++)
tree[i] = nums[i];
for(int i = k / 2 ; i >= 0 ; i --)
adjust(i,k);
for(int i = k ; i < n ; i ++)
{
if(nums[i] > tree[0])
{
tree[0] = nums[i];
adjust(0,k);
}
}
return tree[0];
}
};
当然了,c提供了优先队列可以避免我们手写堆积排序,这里需要注意c默认是大顶堆序,我们需要稍微改变一下优先队列的初始化。
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int,vector<int>,greater<int> > q;
int n = nums.size();
for(int i = 0 ; i < k ; i ++)
q.push(nums[i]);
for(int i = k ; i < n; i ++)
{
if(nums[i] > q.top())
{
q.pop();
q.push(nums[i]);
}
}
return q.top();
}
这个迭代写法有点难理解哦,按照递归写法直接翻译应该是
我试了下,好像都是对的