查找第 i 大元素,除了排序外,可借助快排思想,将其划分,进而分治算法,也可堆排序
借助芯片测试,分治
http://blog.csdn.net/liu1064782986/article/details/7411720
http://blog.csdn.net/atyuwen/article/details/1817600
当有奇数个芯片两两测试,必有一个落单
1. (n-1)/2, 当分组的芯片对淘汰后保留的为奇数
1) 落单为好
奇数个芯片中好的至少比坏的多一个,无所谓加
2) 为坏
不能加
2. 为偶数
1) 落单为好
好的至少等于坏的,加
2) 落单为坏
好的至少壁坏的多两个,无所谓加
To sum up,
奇数时不加,偶数时加
分治算法,注意:
将一组数据划分后,对每个子集求解,复杂度O(logn),而不是,求完第一个子集后,将其解并入第二个子集求解,依此类推,类似顺序法求解数组最大值,复杂度为O(n),这根本不是分治法。
我在分析芯片测试时犯了这错,在比较两片芯片时,是先划分为 n/2组,每组独立比较,这才是分治法
1. 一个数组中位数
public static int chipTest() {
int i = 0, j = 0;
int[] a = copyArray(elements);
int[] tmp = new int[a.length];
while(a.length > 3) {
j = 0;
for(i = 0; i+1 < a.length; i=i+2) {
if(a[i]== a[i+1]) {
tmp[j] = a[i];
j++;
}
}
if(j%2 == 0 && i== a.length-1) {
tmp[j] = a[i];
}
a = copyArray(tmp);
}
if(a.length == 3) {
if(a[0]==a[1]) {
return a[0];
} else {
return a[2];
}
} else if(a.length == 2) {
if(a[0] == a[1]) {
return a[0];
} else {
return -1;
}
} else {
return a[0];
}
}
2. 两个有序数组中位数
http://www.cnblogs.com/luxiaoxun/archive/2012/09/13/2684054.html
顺序法求解, O(n)
float GetMedian(int n) {
int _ia = 0, _ib = 0;
int median1 = 0;
while(_ia < n && _ib < n && _ia+_ib < n) {
if(g_a[_ia]<g_b[_ib]) {
median1 = g_a[_ia];
_ia++;
} else {
median1 = g_b[_ib];
_ib++;
}
}
if(g_a[_ia] < g_b[_ib]) {
return (float)(median1+g_a[_ia])/2;
}
else {
return (float)(median1+g_b[_ib])/2;
}
}
分治法, O(logn)
float GetMedian(int _ia, int _ja, int _ib, int _jb) {
if((_ja-_ia)%2==0 && g_a[(_ia+_ja)/2]==g_b[(_ib+_jb)/2]) {
return g_a[(_ia+_ja)/2];
}
if((_ja-_ia)%2==1 && g_a[(_ia+_ja)/2]+g_a[(_ia+_ja)/2+1]==g_b[(_ib+_jb)/2]+g_b[(_ib+_jb)/2+1]) {
return (float)(g_a[(_ia+_ja)/2]+g_a[(_ia+_ja)/2+1])/2;
}
if(_ja-_ia == 1) {
return (float)(max(g_a[_ia], g_b[_ib])+min(g_b[_ja], g_b[_jb]))/2;
}
if((_ja-_ia)%2==0) {
if(g_a[(_ia+_ja)/2] < g_b[(_ib+_jb)/2]) {
return GetMedian((_ia+_ja)/2, _ja, _ib, (_ib+_jb)/2);
} else {
return GetMedian(_ia, (_ia+_ja)/2, (_ib+_jb)/2, _jb);
}
} else {
if(g_a[(_ia+_ja)/2]+g_a[(_ia+_ja)/2+1] < g_b[(_ib+_jb)/2]+g_b[(_ib+_jb)/2+1]) {
return GetMedian((_ia+_ja)/2+1, _ja, _ib, (_ib+_jb)/2);
} else {
return GetMedian(_ia, (_ia+_ja)/2, (_ib+_jb)/2+1, _jb);
}
}
}
tips
1. 分治算法,复杂度与 logn有关,基本都是递归
2. 递归算法可能有多个终止条件,如本题
3. 当递归到最简形式,亦即某一终止条件
两数组为 a, b
c, d
注意到隐含条件,每个数组有序,a<b,c<d
所以有
return (float)(max(g_a[_ia], g_b[_ib])+min(g_b[_ja], g_b[_jb]))/2;
Error:
没弄懂分治的精髓,在于,不断的大化小,而不是只简化一次。
对于这题,根据两个数组的中位数比较,将规模简化到 O(n+1),就没有进一步化简,这样复杂度仍为 O(n),实际上,根据中位数性质,进一步化简后,原问题的中位数不变,所以可以进一步缩小问题规模
而对于算法书 P48 2.17题,也是用分治,将排序规模减小,但此次减小后即不能化简,所以只能使用一次,为用到递归。
分享到:
相关推荐
线性时间选择,中位数算法,利用按每5个元素分组,分别找出其中位数,再递归找出
条件中位数算法用于无失效数据的可靠性估算,本程序是主函数,将数据带入即可计算
请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。 示例 1: nums1 = [1, 3] nums2 = [2] 则中位数是 2.0 示例 2: nums1 = [1, 2] ...
滤波算法集合(中位数、中位数平均、平均、加权平均、一阶加权、正太分布)
13,15,17,19),其中位数是15,若b=(2,4,6,8,20),其中位数为6。...长有序序列的中位数是含它们所有元素的有序序列的中位数,例如a、b两 个有序序列的中位数为11。设计一个算法求给定的两个有序序列的中 位数。
算法导论,第九章,chp9中位数和顺序统计量,C#和C++代码实现。
算法设计与分析课本上配套的c++版中位数问题~~有注释~希望对大家有帮助
找出两个升序序列的中位数算法理解。 一篇文章带你快速了解!
本文实例讲述了C++实现查找中位数的O(N)算法和Kmin算法,分享给大家供大家参考。具体方法如下: 利用快速排序的partition操作来完成O(N)时间内的中位数的查找算法如下: #include #include #include #include ...
通过用中位数方法来求解,用数学反证法详细证明输油管道的最小代价!
求两个等长升序序列的中位数的实现源码。博客地址:blog.csdn.net/algorithm_only
无线传感器方面比较好的论文,无线传感器网络中位数查询近似算法研究。
现有两个等长升序序列A和B,试设计一个在时间和空间两方面都尽可能高效的算法,找出两个序列的中位数。
(1)设X[0:n-1]和Y[0:n-1]为两个数组,每个数组中含有n个已排好序的数,设计一个算法复杂度为O(logn)的分治算法,找出X和Y中2n个数中的中位数。(中位数:个数为奇数:中间位置上的数;个数为偶数,中间两个数的...
试设计一个O(log n)时间的算法,找出X 和Y 的2n 个数的中位数。 ★数据输入 输入数据第1 行是每个数组中元素个数n;接下来的2 行中每行有n 个整数,分别为X和Y 中元素。 ★数据输出 将计算出的X 和Y 的中位数保留一位...
2)DSA中的Hash函数采用SHA算法。 (1)消息填充:因为我们存储的时候是以字节为单位存储的,所以消息的长度(单位:位)一定是 8 的倍数。而我们填充的时候也一定是 8 位、8 位地来填充。也即不可能只填充一个二...
分治算法分治算法分治算法分治算法分治算法
matlab源代码 基于图像资料数据重建与拟合 基于K均值聚类图像分割 基于中位数算法运动目标检测 基于贝叶斯判别的手写体数字识别 基于主成分分析图像压缩与重建 源代码+训练样本+素材
数字接收机中位同步的插值算法研究,邱健伟,别志松,同步模块是通信系统中的重要部分,一个好的插值算法能提升位同步的性能。论文首先介绍了位同步的基本原理,分析系统中每个模块的
3. 递归的调用selection算法查找上一步中所有中位数的中位数,设为x,偶数个中位数的情况下设定为选取中间小的一个。 4. 用x来分割数组,设小于等于x的个数为k,大于x的个数即为n-k。 5. 若i==k,返回x;若i,在...