问题描述:无序找第k小的数?
1、解法一
先排好序,再找第k小个数;返回A[k-1];此解法的时间复杂度为:O(nlogn);
2、解法二
情况一:k = 1 和 k = n 就是找数组的最小值和最大值;
情况二:找出中位数
3、找中位数(随机选择算法)
利用快速排序的原理,一轮排序,有2种情况:
if i = k-1;返回a[i];
if i != k-1;左边/右边递归查找,时间复杂度为:O(n);
具体思想:
分析:在大多数情况下的时间复杂度是:O(n);但是最坏情况,完全顺序下找第k = n-1大数,此时的时间复杂度是:O(n^2);
4、无序找第k小值
快排的升序实现思想,在加上递归查找;
(1)、代码实现
#include<stdio.h> void findKSmall(int *a, int start, int end, int key); void findKSmall(int *a, int start, int end, int key){ int i = start; int j = end; int tmp = a[i]; //快排中的升序 while(i < j){ while(i < j && a[j] > tmp){ j--; } if(i < j){ a[i++] = a[j]; } while(i < j && a[i] < tmp){ i++; } if(i < j){ a[j--] = a[i]; } } a[i] = tmp; if(key-1 < i){ findKSmall(a, 0, i-1, key); }else if(key-1 > i){ findKSmall(a, i+1, end, key); }else{ return; } } void main(void){ int a[] = {8, 4, 6, 9, 2, 3, 7, 9, 11, 10}; int count = sizeof(a)/sizeof(int); int k; int i; printf("请输入要查找的第k小的数:"); scanf("%d", &k); findKSmall(a, 0, count-1, k); for(i = 0; i < count; i++){ printf("%d ", a[i]); } printf("\n%d\n", a[k-1]); }
结果截图
5、无序找第k大值
快排的降序实现思想,在加上递归查找;
(1)、代码实现
#include<stdio.h> void findKBigger(int *a, int start, int end, int key); void findKBigger(int *a, int start, int end, int key){ int i = start; int j = end; int tmp = a[i]; //快排中的降序 while(i < j){ while(i < j && a[j] < tmp){ j--; } if(i < j){ a[i++] = a[j]; } while(i < j && a[i] > tmp){ i++; } if(i < j){ a[j--] = a[i]; } } a[i] = tmp; if(key-1 < i){ findKBigger(a, 0, i-1, key); }else if(key-1 > i){ findKBigger(a, i+1, end, key); }else{ return; } } void main(void){ int a[] = {8, 4, 6, 9, 2, 3, 7, 9, 11, 10}; int count = sizeof(a)/sizeof(int); int k; int i; printf("请输入要查找的第k大的数:"); scanf("%d", &k); findKBigger(a, 0, count-1, k); for(i = 0; i < count; i++){ printf("%d ", a[i]); } printf("\n%d\n", a[k-1]); }
(2)、结果截图
6、线性算法
(1)、划分为5个一组的元素,在找出每一组的中值(对这5个数进行排序,找出中值),时间复杂度:O(n)
(2)、用递归去找这些中值中的那一个中值(中值中的中值);
(3)、此时用这个最中值的下标和k作比较,之后和上面的随机选择算法一样!!!
具体模型如下:
算法分析
找中值和第k小数时间复杂度均为:O(n);比较好的解决了上述最坏时间复杂度为O(n^2)的情况;
3个元素一组的话,结果不成立;
5是这个算法能成功的最小数字,7个元素为一组算法也能成立,但是性能不会有所提高;
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。