无序数组中第K大的数

时间:2022-05-16 10:54:48

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