问题描述:
找出一个数组中第K小的元素,时间复杂度为O(n)。
解法:
1.首先大家都会想到的解法是排序,之后找出第k个元素,但是排序的时间复杂度不符合要求,或者需要额外的空间。
2.利用快排的思想,以枢纽(随机得到)为界,将数组分为2部分,一部分小于等于这个枢纽值,一部分大于这个枢纽值,与快排不同的是,我们只处理一部分,另一部分舍弃。
代码如下:
#include<iostream> #include<algorithm> #include<time.h> #include<cstring> #define random(x) (rand()%x) //生成随机数用的using namespace std;//交换两个数的值void swap(int arr[], int i, int j) {int tem;tem = arr[i];arr[i] = arr[j];arr[j] = tem;}int partition(int arr[], int L, int R) {int less = L - 1;int more = R;while (L < more) {if (arr[L] < arr[R]) {swap(arr, ++less, L++);}else if (arr[L] > arr[R]) {swap(arr, --more, L);}else {L++;}}swap(arr, more, R);//将枢纽从最后的位置移动到分界处int p = more;return p; //返回枢纽的位置}int quicksort_select(int arr[], int L, int R,int k) {srand((int)time(0));//种子,为了每次生成的随机数不同if (k > (R - L + 1) || k < 1) {return -1;}int P;if (L < R) {swap(arr, L + (int)(random(1000) / (float)(1000)*(R - L + 1)), R); //生成一个随机数,再把随机数所在位置的数与数组最后一个数交换P = partition(arr, L, R);}int j = P - L + 1;if (j == k) {return arr[P];}else if (j>k) {quicksort_select(arr, L, P, k);}else {quicksort_select(arr, P + 1, R, k - j);}}int main() {//textint a[5] = { 1,2,3,4,5 };int m=quicksort_select(a, 0, 4, 2);cout << m;}
代码分析如下:
partition函数返回枢纽的坐标P,P-L+1是左半部分元素的个数,这部分的元素都小于等于枢纽的值,右半部分的元素值都大于枢纽的值,如果j<P-L+1说明第j个小的元素,在左半部分,让后只需要递归的处理左半部分即可,如果P等于j,那么很幸运,枢纽的值就是我们的所求,如果j>P-L+1,说明第k个小的元素在右半部分,指的注意的是,我们所求的数是右半部分第j-(P-L+1)小的数,我们这时候处理右半部分即可。这种方法在平均的时间复杂度是O(n)(证明看《算法导论》),但他有一个额外的产生随机数,这个的效率据说很低(没有亲自探测);
3.采用中位数线性时间选择,我放到下一篇文章。