问题
求解乱序数组中第k个数
利用堆实现
时间复杂度是\(O(nlogk)\)。以求第K大的数为例，建立小根堆，即堆顶元素为当前遍历的数字中最小值，当堆的长度大于k时，弹出堆顶元素，最后返回堆顶元素即可
在C++中直接使用优先队列 priority_queue即可
手写堆
为了实现类似的功能，手写堆需要提供3个接口，分别是pop()、top()、push()
当pop()堆顶元素过后，需要将最后一个元素，放在堆顶，然后重新调整堆的结构
当push()一个元素后，先在堆最后开辟一个空间，然后为这个元素寻找合适位置，调整堆的结构
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e9+5;
vector<int> h(N);
//堆的大小
int m = 0;
//小根堆 index为下标位置
//up操作 实现push后的位置调整
//对于下标index其父节点下标就是index/2
void up(int index)
{
while(index/2 > 0 && h[index] < h[index/2])
{
swap(h[index/2],h[index]);
index /= 2;
}
}
//down操作 实现pop后调整位置
//寻找index下标位置的合适位置，即向下寻找
void down(int index)
{
while(index <= m)
{
int cur = index;
if(index*2 <= m && h[cur] > h[index*2]) cur = index*2;
if(index*2+1 <= m && h[cur] > h[index*2 + 1]) cur = index*2 + 1;
if(index == cur) break;
swap(h[cur],h[index]);
index = cur;
}
}
//实现push接口
void push(int val)
{
h[++m] = val;
//调整val的位置
up(m);
}
//实现top接口
int top()
{
return m >= 1 ? h[1] : -1;
}
//实现pop接口
void pop()
{
//将最后的元素替代顶部元素
h[1] = h[m--];
//调整位置
down(1);
}
堆排序
堆排序其实和上述方法类似，其时间复杂度为\(O(nlogn)\)，不稳定
通过将数组构成一个大顶堆，然后交换堆顶和最后一个数，那么此时最大值就排好了位置，然后再对0~n-1个数进行重复操作。
- 将数组构建为大顶堆
- 交换堆顶元素和数组末尾元素
- 将剩余的0~n-1个数重新构成大顶堆，然后重复直到有序
//构建大顶堆
//原始数组，待调整下标pa，数组大小
void makeheap(vector<int>& nums,int pa, int n)
{
int temp = nums[pa];
//循环变量
int parent,child;
for(parent = pa;(parent*2+1)<n;parent = child)
{
//寻找最大的子节点
child = 2*parent+1;
if(child != n-1 && nums[child] < nums[child+1])
{
child++;
}
if(temp >= nums[child])
{
break;
}
else{
nums[parent] = nums[child];
}
}
nums[parent] = temp;
}
//堆排序
void heapsort(vector<int>& nums,int n)
{
//建立最大堆
for(int i = n/2-1;i>=0 ;i--)
{
makeheap(nums,i,n);
}
//移动大值到最后，重新构建大顶堆
for(int i = n-1;i>=0;i--)
{
swap(nums[i],nums[0]);
makeheap(nums,0,i);
}
}
快速排序实现
时间复杂度为O(n)，就是通过基准将数组分为两部分，然后当小于基准的部分长度大于k，那么就在小于的部分递归寻找，大于k就在大于基准的部分递归寻找
int quick_sort(vector<int>& nums,int l,int h,int k)
{
if(l==h) return nums[l];
int i = l-1;
int j = h+1;
int mid = nums[l+h >> 1];
while(i<j)
{
while(nums[++i] < mid);
while(nums[--j] > mid);
if(i<j) swap(nums[i],nums[j]);
}
//l...j j+1...h
int len = j-l+1;
if(len >= k) return quick_sort(nums,l,j,k);
else return quick_sort(nums,j+1,h,k-len);
}
总结
可以看到
对于堆排序，可以去寻找第K大的数
对于快速选择，可以去寻找第K小的数
当然如果长度为n，第K大的数也是第n-k+1小的数