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; }