中位数

algorithm

题目

设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]

代码

/**
 * @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];
    }
}