无序数组中第K大的数
1. 排序法
时间复杂度 O(nlogn)
2. 使用一个大小为K的数组arr保存前K个最大的元素
遍历原数组，遇到大于arr最小值的元素时候，使用插入排序方法，插入这个元素
时间复杂度，遍历是 O(n), 插入 O(K), 所以时间复杂度 O(nK)
3. 二叉堆--小顶堆
维护一个有K个元素的小顶堆，堆顶就是最小值。
遍历剩余 n-K 个元素，大于堆顶就插入堆并调整。
时间复杂度是遍历 O(n-K), 调整堆 O(K), 所以时间复杂度 O( (n-K)log(K) )
4. 分治法
类似快速排序，找到一个key，把数组中大于key的放在前面，小于key的放在后面
如果key的下标正是要找的K，结束。否则，K小于key下标的话，递归处理前半部分，否则，递归处理后半部分
时间复杂度是 o(n)
#include <iostream>
#include <cstring>
using namespace std;
int func(int *arr, int l, int r, int k)
{
if (k-1 < l || k-1 > r)
{
return -1;
}
int p = l;
int key = arr[r];
for (int i = l; i < r; ++i)
{
if (arr[i] > key)
{
int tmp = arr[p];
arr[p] = arr[i];
arr[i] = tmp;
p++;
}
}
if (p == k-1)
{
return key;
}
else if (p > k-1)
{
return func(arr, l, p-1, k);
}
else
{
arr[r] = arr[p];
return func(arr, p+1, r, k);
}
}
int main()
{
int arr[] = {12,43,56,7,90,7,0,8,58,32,21};
int len = sizeof(arr) / sizeof(int);
int *tmp = new int[len];
for (int i = -1; i <= len+1; ++i)
{
memcpy(tmp, arr, sizeof(arr));
cout << func(tmp, 0, len-1, i) << ' ';
}
delete[] tmp;
return 0;
}