免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 1631 | 回复: 0

[算法] 寻找随机数列中的某一数字 [复制链接]

论坛徽章:
0
发表于 2013-10-23 00:18 |显示全部楼层
3、进一步泛化,在一组随机排列的数中找出第k小的,这个元素称为k-th Order Statistic。能想到的最直观的算法肯定是先把这些数排序然后取第k个,时间复杂度和排序算法相同,可以是Θ(nlgn)。这个问题虽然比前两个问题复杂,但它也有平均情况下时间复杂度是Θ(n)的算法,将上一节习题1的快速排序算法稍加修改就可以解决这个问题:

/* 第k小的元素在start和end之间,找出并返回该元素 */
int order_statistic(int start, int end, int k)
{
        用partition函数把序列分成两部分,中间的pivot元素是序列中的第i个;
        if (k == i)
                返回找到的元素;
        else if (k > i)
                第k小的元素在序列后半部分,找出并返回该元素;       
        else
                第k小的元素在序列前半部分,找出并返回该元素;
}

快速排序<quickSort.cpp>:
  1. #ifndef QUICKSORT_H
  2. #define QUICKSORT_H
  3. class quickSort{

  4.     private:
  5.     int * a,LEN;

  6.     public:
  7.     quickSort(int * array,int length):a(array),LEN(length){}
  8.     ~quickSort(){}
  9.     void quicksort(int start,int end);
  10.     int partition(int start,int end);
  11. };

  12. int quickSort::partition(int start,int end){
  13.     int pivot=a[start],temp=0;
  14.     int i=start,j=end;
  15.     while(i<j){
  16.         if(a[i]>pivot){
  17.            temp=a[i];
  18.            a[i]=a[j];
  19.            a[j--]=temp;
  20.         }
  21.         else i++;
  22.     }
  23.     if(a[i]>pivot)i--;
  24.     a[start]=a[i];
  25.     a[i]=pivot;
  26.     return i;
  27. }

  28. void quickSort::quicksort(int start,int end){
  29.     int mid;
  30.     if(end>start){
  31.         mid=partition(start,end);
  32.         quicksort(start,mid-1);
  33.         quicksort(mid+1,end);
  34.     }
  35. }
  36. #endif
复制代码
找数字<t_find.cpp>:
  1. #include <stdio.h>
  2. #include "quickSort.cpp"

  3. const int LEN=8;
  4. int a[]={4,2,12,7,1,10,9,3};
  5. quickSort t_q(a,LEN);

  6. int order_statistic(int start,int end,int k){
  7.     int mid=t_q.partition(start,end);
  8.     if(mid==k)return a[k];
  9.     else if(k>mid)order_statistic(mid+1,end,k);
  10.     else order_statistic(start,mid-1,k);
  11. }

  12. int main(void){
  13.     printf("%d\n",order_statistic(0,7,1));
  14. }
复制代码
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP