中位数与第K小元素

算法实际上是模仿快速排序算法设计出来的,其基本思想也是对输入数组进行递归划分,与快速排序不同的是,它只对划分出来的子数组之一进行递归处理;

int randompartition(int a[],int l,int r)
{
    int i=l-1,j=r,v=a[r],tmp;
    for(;;)
    {
        while(a[++i]<v);
        while(a[--j]>v)if(j==l)break;
        if(i>=j)break;
        tmp=a[i];
        a[i]=a[j];
        a[j]=tmp;
    }
    tmp=a[i];a[i]=a[r];a[r]=tmp;
    return i;
}

randompartition产生的划分基准是随机的,在这个条件下,可以证明算法randomselect可以在o(n)平均时间内找出n个输入元素的第k小元素。

消除randomselect尾递归的算法如下:

 1 int randomselect(int a[],int l,int r,int k)
 2 {
 3     int i,j;
 4     while(l<r)
 5     {
 6         i=randompartition(a,l,r);
 7         j=i-l+1;
 8         if(j==k)
 9             return a[i];
10         if(j>k)
11             r=i-1;
12         else
13         {
14             l=i+1;
15             k-=j;
16         }
17     }
18     return ((r<i)?a[l]:a[r]);
19 }

解决算法与数据结构实验题10.1神谕者:

 1  
 2             #include<stdio.h>
 3 int a[50005];
 4 int randompartition(int a[],int l,int r)
 5 {
 6     int i=l-1,j=r,v=a[r],tmp;
 7     for(;;)
 8     {
 9         while(a[++i]<v);
10         while(a[--j]>v)if(j==l)break;
11         if(i>=j)break;
12         tmp=a[i];
13         a[i]=a[j];
14         a[j]=tmp;
15     }
16     tmp=a[i];a[i]=a[r];a[r]=tmp;
17     return i;
18 }
19 int randomselect(int a[],int l,int r,int k)
20 {
21     int i,j;
22     while(l<r)
23     {
24         i=randompartition(a,l,r);
25         j=i-l+1;
26         if(j==k)
27             return a[i];
28         if(j>k)
29             r=i-1;
30         else
31         {
32             l=i+1;
33             k-=j;
34         }
35     }
36     return ((r<i)?a[l]:a[r]);
37 }
38 int main()
39 {
40     int n,m,i,len,x,y;
41     scanf("%d %d",&n,&m);
42     for(i=0;i<n;i++)
43     {
44         scanf("%d",&a[i]);
45     }
46     len=n;
47     for(i=0;i<m;i++)
48     {
49         scanf("%d %d",&x,&y);
50         if(x==0)
51             a[len++]=y;
52         else
53             printf("%d\n",randomselect(a,0,len-1,y));
54     }
55     return 0;
56 
57 }
58 
59         
View Code

 

 

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
01-12 12:42
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议