阅读 182

算法系统学习-找第k小值(非等分分治)

前言

????????‍???? 该系列是基于有一定语言基础(C,C++,Java等等)和基本的数据结构基础进行的算法学习专栏,如果觉得有点吃力 ???? ,建议先了解前提知识再学习喔!本个专栏会将用更容易理解的表达去学习算法,如果在一些表述上存在问题还请各位多多指点 ????????‍???? ,要是觉得还不错记得点个 ????本专栏快捷门:juejin.cn/column/7024…

非等分二分法

现实中常见的应用就是寻找中值元素(中值是一个很有用的统计量,例如中间工资,中间年龄,中间重量等),因此经常会遇到在“一组数据中取第k小的值”。

按照以前的最好的排序算法的复杂性是O(nlogn),但我们可以利用二分法将复杂度降为O(n),可这个二分法不是简单典型的二分法分解成完全独立,相似的两个问题,因为在选出分解后第一组的第k小的数据和第二组的第k小的数据,不能保证这两个数据之一是原问题的解。

Case1:

求一组数的第二小的数

算法分析:

在用二等分法分解的两个子集中,无论只选取第二小数据或只选取最小的数据,合并处理后都有可能得不到原问题的解。但若在两个子集中都选取最小的两个值,那原问题中第二小的数据则一定在这四个数据中。由此,将问题转化成“求一组数中较小的两个数”后,二等分法分解就可将原问题“分解为原问题独立且相似的两个问题”。

这样,回溯合并的过程就是从两个子问题选出的共4个数中,选取出较小的两个数,直到回溯结束,就得到一组数中较小的两个数,从而得到了原问题的解。


算法设计:

float a[100]; main(){     int n;     float min2;     cin>>n;     for(i=0;i<n-1;i++){     cin>>a[i];     }     min2=second(n);     cout<<min2; } second(int n){ float min2,min1;     two(0,n-1,min2,min1);     return min2; } two(int i,int j, float &fmin2,float &fmin1){ float lmin2,lmin1,rmin2,rmin1;     int mid;     if(i=j){      fmin2=fmin1=a[i];     }else if(i=j-1){      if(a[i]<a[j]){         fmin2=a[j];         fmin1=a[i];         }else{         fmin2=a[i];         fmin1=a[j];         }     }else{     mid=(i+j)/2;     two(i,mid,lmin2,lmin1);     two(mid+1,j,rmin2,rmin1);         if(lmin<rmin1){          if(lmin2<rmin1){                 fmin1=lmin;                 fmin2=lmin2;             }else{             fmin1=lmin1;             fmin2=rminl;             }         }else{         if(rmin2<lmin1){         fmin1=rmin1;         fmin2=rmin2;         }else{         fmin1=rmin1;         fmin2=lmin1;                  }         }     } } 复制代码

小结:

以上算法利用“分解为与原问题相似的两个子问题”的技巧,解决了一个个简单的排序问题。但对于选取第k小元素的问题,则从效率上是无法行得通的。难道就不能使用二分法解决这类问题?分治法中当然不仅仅包括二分法,也可以使用“非等份分解方法”的例子

Case2:

对于给定的n个元素的数组a【0:n-1】,要求从中找出第k小的元素,要求找到第k小的元素

问题分析:

选择问题的一个应用就是寻找中值元素,此时k=【n/2】。我们可以首先选取第一个数作为分界数据,将比它小的数据存在它的左边,将比它大的数据存储在右边,它存储在左右两个子集之间。(类似荷兰国旗问题)这样左右子集就是原问题分解后的独立子问题,再用同样的方法,解决这些子问题。知道每个子集只有一个数据,自然就有序了,也就完成了全部数据的排序工作。

可以通过改写快排算法,一趟排序分解出的左子集中元素个数left,可能有一下三种情况:

  1. nleft=k-1 ,则分界数据就是选择问题的答案

  2. nleft>k-1,则选择问题的答案继续在左子集中找,问题规模变小了

  1. nleft<k-1,则选择问题的答案继续在右子集中找,问题变成选择第k-nleft-1小的数,问题的规模也变小了

算法设计:

xzwt(int a[],int n,int k)  //返回a【0:n-1】中第k小的元素 {    if(k< 1|| k>n){ error(); }  return select(a,0,n-1,k);    } select (int a[],int left,int right,int k){ //在a【left:right】中选择第k小的元素          if(left >=right){     return a[left];     }     int i=left;//从左至右的指针     j=right+1;//从右至左的指针     int pivot =a[left];     while(1){      do{             //在左侧寻找>=pivot的元素         i=i+1;         }while(a[i]<pivot);         do{         j=j-1;         }while(a[j]>pivot);//在右侧寻找<=pivot的元素         if(i>=j){         break;//未发现交换对象         }        Swap(a[i],a[j]);          }     if(j-left+1=k){     return pivot;     }     a[left]=a[j];//设置pivot     a[j]=pivot;     if(j-left+1<k){ 。//对一个段进行递归调用     return select(a,j+1,right,k-j-1+left);     }else{     return select(a,left,j-1,k);     } }


作者:GTW_Zeus
链接:https://juejin.cn/post/7028754736664838151

文章分类
代码人生
文章标签
版权声明:本站是系统测试站点,无实际运营。本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 XXXXXXo@163.com 举报,一经查实,本站将立刻删除。
相关推荐