题目

设X[0: n-1]和Y[0: n-1]为两个数组，每个数组中含有n个己排好序的数。试设计一个〇(logn)时间的分治算法，找出X和y的2n个数的中位数，并证明算法的时间复杂性为〇(logn)

思路

本题目已说明时间复杂度为〇(logn)，因此不是简单地遍历，因此选中二分来解题。

当数组中数字个数为偶数时

数字代表位置，而不是大小
X: 1,2,3,4
Y:11,22,33,44
将X,Y合并时，新数组共有8个数字，也就是中位数是第4个数字

分情况讨论:

  • 2 == 22
    中位数一定是2或者22

  • 2 > 22
    中位数可能是1,2,33,44
    因为22最好的情况是比1,11大，不可能是中位数
    同理11不可能是中位数
    而3已经比1,2,11,22这4个数大，不可能是中位数
    同理4也不能
    因此得到二分区间[1,2]和[33,44]

  • 2 < 22
    中位数可能是11,22,3,4
    因此得到二分区间[11,22]和[3,4]

当数组中数字个数为奇数时

数字代表位置，而不是大小
X: 1,2,3,4,5
Y:11,22,33,44,55
将X,Y合并时，新数组共有10个数字，也就是中位数是第5个数字

分情况讨论:

  • 3 == 33
    中位数一定是3或者33

  • 3 < 33
    中位数可能是11,22,3,4,5
    因为33已经比1,2,3,11,22这5个数大了，一定不是中位数
    同理44,55不是中位数
    而2最好的情况是大于1,11,22，最多可能是第4个数，也不能是中位数
    同理1不是中位数
    因此得到二分区间[11,22]和[3,4,5]
    但是这样的区间个数不相等，无法递归
    因此该区间为[11,22,33]和[3,4,5]
    尽管33不可能是中位数，但是为了递归只能算进去

  • 3 > 33
    中位数可能是1,2,33,44,55
    因此得到二分区间[1,2,33]和[33,44,55]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * @param a 数组a
 * @param as 数组a第一个数的下标
 * @param ae 数组a最后一个数的下标
 * @param b 数组b
 * @param bs 数组b第一个数的下标
 * @param be 数组b最后一个数的下标
 * @return 合并后中位数
 */
public int find (int []a, int as, int ae, int []b, int bs, int be){
	int len = ae - as + 1;
	int amid = as + len/2;
	int bmid = bs + len/2;
	
	if(len == 1){
		return Math.min(a[amid], b[bmid]);
	}
	
	//奇偶标志位
	int flag = 0;
	if(len%2 == 0){
		amid -= 1;
		bmid -= 1;
		flag = 1;
	}
	
	if(a[amid] > b[bmid]){
		return find(a, as, amid, b, bmid + flag, be);
	}else if(a[amid] < b[bmid]){
		return find(a, amid + flag, ae, b, bs, bmid);
	}else{
		return a[amid];
	}
}