注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Hao的博客

I'm on my way……

 
 
 

日志

 
 
 
 

寻找第K小的数  

2009-03-22 23:05:20|  分类: Algorithm discov |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

今天在做题目的时候碰到了这么一道题,求一堆数中中间的那个数。题目很简单,只要用个现成的快速排序就是了。但是时间复杂度却不是那么的满意。加上今天看了编程之美上的一个关于寻找最大的K个数的问题,决定借鉴它上面的思想自己写个函数实现寻找第K小的数。就当练练手吧~~~~~

主要思想:只要求找出第K小的数,则可以通过避免对所有的数排序来减少时间复杂度,借鉴快速排序的思想,通过中间数将集合中的数一分为二(这里为了方便就选取集合的第一个数作为中间数),一个集合的数都大于中间数(记为nExSet),另一个集合的数都小于中间数(记为nSet),如果nSet元素个数大于等于K,说明我要找的第K小的数必在这个集合内,否则一定在nExSet内,且我只要找nExSet集合中的第(K-nSet元素个数)个数就可以了

代码如下:

int nSet[MAX];
int nExSet[MAX];

int kthSmall(int set[],int n,int k){
    int i,j,r,m=set[0];
    while(n!=1){    //当前查找的集合元素的个数不为1时,继续处理;为1时就意味着找到了
        m=set[0];    //m作为中间元素
        j=r=0;
        for(i=1;i<n;i++){//
遍历集合
            if(set[i]>m)nExSet[j++]=set[i];//如果当前元素比m大,就将当前元素加入nExSet
            if(set[i]<=m)nSet[r++]=set[i];//反之就加入到nSet,这里没有考虑set[0],目的如下
        }
        if(j==0)nExSet[j++]=m;//if...else主要是为了防止m大于或小于其他所有元素的情况
        else nSet[r++]=m;
  
/*如果nSet集合中的元素个数大于K,说明第K小的元素必在其中
   *否则一定在nExSet中,且应该是nExSet集合中第k-r小的元素
   *更新相应的变量
  */
       if(r>=k){
           n=r;
           for(i=0;i<n;i++)set[i]=nSet[i];
        }

        else{
            n=j;
            for(i=0;i<n;i++)set[i]=nExSet[i];
            k=k-r;
        }
    }
    return set[0];
}

注意问题:在二分集合时,有可能出现极端的情况,如有序的时候,如果采用简单的二分,会导致死循环,而且需要考虑有重复元素的情况,这些问题都已经在代码中标注出来了

写完这个函数后,总觉的是对的,经过一些数据测试也没找出什么问题,可是提交的时候总是wrong answer,实在是郁闷啊,只能等明天再来解决了

  评论这张
 
阅读(1298)| 评论(3)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017