`

找中位数相关算法

 
阅读更多
查找第 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题,也是用分治,将排序规模减小,但此次减小后即不能化简,所以只能使用一次,为用到递归。
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics