数组中求第K大数的实现方法
问题:有一个大小为n的数组A[0,1,2,…,n-1],求其中第k大的数。
该问题是一个经典的问题,在《算法导论》中被作为单独的一节提出,而且其解决方法很好的利用了分治的思想,将时间复杂度控制在了O(n),这多少出乎我们的意料,此处暂且不表。
该问题还可以变形为:有一个大小为 n的数组A[0,1,2,…,n-1],求其中前k大的数。
一字之差,原问题是“第k大”,变形的问题是“前k大”,但是平均时间复杂度却都可以控制在O(n),这不由得让人暗暗称奇。
我们先分析原问题:有一个大小为 n的数组A[0,1,2,…,n-1],求其中第k大的数。
我们先取特例,令k=1,那么就是取最大的数,只要扫描一遍数组就可以确定该值,如果k=2,则扫描两边数组就可以确定第二大的数,依此类推下去,时间复杂度是O(k*n),如果k跟n是一个数量级,那么时间复杂度就是O(n*n)了,显然不是最优的解法。
考虑分治法,难点在于如何将该问题分解为两个子问题。
快速排序最基础的一步:
随机取某一个数x,将其与数组末尾元素交换,然后将比其小的数交换至前,比其大的数交换至后。
这一步使某一数组的快速排序问题分解成两个子数组的排序问题,现在我们就依此来解决取第k大的数这个问题。
设数组下表从0开始,至n-1结束。
1、 随机取某个数,将其与数组末尾元素交换。
a) idx=rand(0,n-1);生成[0,n-1]间的随机数。
b) Swap(array[idx], array[n-1]);
2、 用末尾元素x,将比x小的数交换至前,比x大的数交换至后,并返回此时x在数组中的位置mid。
3、 如果mid==n-k,那么返回该值,这就是第k大的数。
如果mid>n-k,那么第k大的数在左半数组,且在左半数组中是第k-(n-mid)大的数。
如果mid<n-k,那么第k大的数在右半数组,而且仍然是第k的数。
#include "iostream"
using namespace std;
int random_partion(int *p, int n)
{
int idx=rand()%n;
swap(p[idx], p[n-1]);
int i=-1; //i表示最后一个小于p[n-1]的元素的位置
int j=0; //j用来扫描数组
for(j=0; j<n; j++)
{
//将小于p[n-1]的数交换到前半部分
if(p[j]<p[n-1])
{
swap(p[++i], p[j]);
}
}
swap(p[++i], p[n-1]);
return i;
}
int getMaxK(int *p, int n, int k)
{
int mid;
if(k<=0)
return -1;
if(n<k)
return -1;
mid=random_partion(p, n); //对原数组进行一次划分
if(mid == n-k) //如果mid==n-k,那么返回该值,这就是第k大的数
return p[mid];
else if(mid<n-k)
return getMaxK(p+mid+1, n-mid-1, k); //如果mid<n-k,那么第k大的数在右半数组,而且仍然是第k大数
else
return getMaxK(p, mid, k-(n-mid)); //如果mid>n-k,那么第k大的数在左半数组,且在左半数组中是第k-(n-mid)大的数
}
int main(void)
{
int num,a[] = {12012, 3, 945, 965, 66, 232, 65, 7, 8, 898, 56, 878, 170, 13, 5};
num=getMaxK(a, 15, 4);
printf("%d\n",num);
system("pause");
return 0;
}
您可能感兴趣的文章
- 01-10求子数组最大和的解决方法详解
- 01-10深入第K大数问题以及算法概要的详解
- 01-10如何寻找数组中的第二大数
- 01-10深入线性时间复杂度求数组中第K大数的方法详解
- 01-10深入理解数组指针与指针数组的区别
- 01-10c语言字符数组与字符串的使用详解
- 01-10解析sizeof, strlen, 指针以及数组作为函数参数的应用
- 01-10c语言中用字符串数组显示菜单的解决方法
- 01-10探讨C++中数组名与指针的用法比较分析
- 01-10求数组中最长递增子序列的解决方法
阅读排行
本栏相关
- 04-02c语言函数调用后清空内存 c语言调用
- 04-02func函数+在C语言 func函数在c语言中
- 04-02c语言的正则匹配函数 c语言正则表达
- 04-02c语言用函数写分段 用c语言表示分段
- 04-02c语言中对数函数的表达式 c语言中对
- 04-02c语言编写函数冒泡排序 c语言冒泡排
- 04-02c语言没有round函数 round c语言
- 04-02c语言分段函数怎么求 用c语言求分段
- 04-02C语言中怎么打出三角函数 c语言中怎
- 04-02c语言调用函数求fibo C语言调用函数求
随机阅读
- 01-10使用C语言求解扑克牌的顺子及n个骰子
- 01-10delphi制作wav文件的方法
- 08-05dedecms(织梦)副栏目数量限制代码修改
- 08-05DEDE织梦data目录下的sessions文件夹有什
- 01-11Mac OSX 打开原生自带读写NTFS功能(图文
- 01-10C#中split用法实例总结
- 08-05织梦dedecms什么时候用栏目交叉功能?
- 04-02jquery与jsp,用jquery
- 01-11ajax实现页面的局部加载
- 01-10SublimeText编译C开发环境设置