首页 > 代码库 > 中位数和顺序统计,以线性期望时间做选择
中位数和顺序统计,以线性期望时间做选择
找出一个数组的最大值和最小值是比较容易的,我们只需遍历一次数组即可。但是寻找一个数组的第i小或者第i大,就需要一些技巧使得查找的时间尽可能小。随机化划分选择算法是一个时间复杂度为O(n)的算法。
int fIndmax(int a[],int p,int r,int i) { if(p==r) return a[p]; int q = RandPartition(a, p, r); // A[q]作为主元将A[p...r]进行划分。 int k = q - p + 1; //假设k是要查找的第i小的元素 if(i==k) //如果K=i则主元就是目标元素,如果i<k,则递归地求解左边的序列,如果i>k则递归求解右边的序列 return a[q]; else if(i<k) { return fIndmax(a, p, q-1, i); } else return fIndmax(a, q+1, r, i-k); }
这个算法的缺点是:如果一个数组中又重复元素,那么得到的结果不是我们期望的结果。解决方法是先删除数组中重复的元素,再利用本算法。 应该还有更好地方法!
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。