Say Hi

找中位数

题目

/*Just find the median value of the array Result.

E.g. given array A = [1, 3, 5, 6, 7] and array B = [2, 3, 9], the array Result = [1, 2, 3, 3, 5, 6, 7, 9], the median value is 4.

Requirements:

·You should not change array A and B.

·In order to save memory, array Result is not given and you are not allowed to allocate any other arrays.

·Minimize the time complexity.

You can code in any language you like. Your function may look like this:

int findMedian(int lengthOfA, int A[lengthOfA], int lengthOfB, int B[lengthOfB])*意思就是两个有序的数组A和B，求这两个数组的中位数；比如A = [1, 3]，B = [2]，那么中位数就是2；如果A = [1, 5，7]，B = [2，3，4]，那么中位数就是（3+4）/2 = 3.5；实现的github链接：https://github.com/dy21335/algorithm/blob/master/js/topk.js思路首先

对于arr1和arr2两个数组，设两个数组的总长为sumLen，中位数为为第k个数：

如果sumLen为基数，则;

如果sumLen为偶数，则

现在关键就是怎么在不用把两个数组进行合并的前提下，来找这第k个数？我们采用二分查找的思想。

首先找出两个数组的中间值，分别为和；假设key1

为了表述清楚，可以参考下图，，分别为两个数组在key1和key2之前的长度:

现在讨论x+y+1与k的关系

如果x+1+y>=k，则k肯定是在key2前面；假设两个数组合并以后的样子如下图，为合并后的数组的在key2前的长度，len>=x+1+y：

也就是说k不可能出现arr2数组key2后面的黄色区域，所以可以把arr2的后半部分删掉，那么新的查找就是在如下两个数组中查找第k个值：

如果x+1+y

而x+y+1

所以新的数组排序就是如下图，去找第个值；

我们先来看key1有可能到达的最远的距离，key1最远能到达的距离就是arr1中key1之前的元素和arr2中key2之前的元素都在它前面，比如如下图；

最后就是一个迭代的过程啦～

出口

最后递归的出口就是当其中一个数组都遍历完了的时候，也就是的时候，k值就在另外一个数组中；比如arr1遍历完了，那个中位数就是,start为数组的索引开始处；

最后附上用js实现的代码：

function findMedian(arr1, arr2) {

var len1 = arr1.length,

len2 = arr2.length,

sumLen = len1 + len2;

if (sumLen & 1) {

return findKth(arr1, 0, len1-1, arr2, 0, len2-1, parseInt(sumLen / 2 + 1));

}

return (findKth(arr1, 0, len1-1, arr2, 0, len2-1, parseInt(sumLen / 2)) + findKth(arr1, 0, len1-1, arr2, 0, len2-1, parseInt(sumLen / 2 + 1))) / 2;

}

function findKth(arr1, start1, end1, arr2, start2, end2, k) {

if (start1 > end1) {

return arr2[start2 + k - 1];

}

if (start2 > end2) {

return arr1[start1 + k - 1];

}

var median1 = parseInt((end1 - start1 + 1) / 2),

median2 = parseInt((end2 - start2 + 1) / 2),

key1 = start1 + median1,//如果是偶数个，则key1取得是向上取整的数，如果是基数个，则是刚好在中间

key2 = start2 + median2,

sum_len = median1 + median2 + 1;

console.log("arr1的start1：" + start1 + " end1: " + end1 + " median值： " + median1 + " key1: " + key1 +

" **arr2的start2： " + start2 + " end2: " + end2 + " median值： " + median2 +" key2 " + key2

+ " k值： " + k + " sum_len值： " + sum_len );

console.log("~~~~~~~~~~~~~~~~~~~~~");

if (arr1[key1]

if (sum_len >= k) {

return findKth(arr1, start1, end1, arr2, start2, key2 - 1, k);

}

else {

return findKth(arr1, key1 + 1, end1, arr2, start2, end2, parseInt(k - median1-1));

}

}

else if (arr2[key2]

if (sum_len >= k) {

return findKth(arr1, start1, key1 - 1, arr2, start2, end2, k);

}

else {

return findKth(arr1, start1, end1, arr2, key1 + 1, end2, parseInt(k - median2-1));

}

}

}

//查找两个排序数组中的第K个元素

var arr1 = [1, 2, 3],

arr2 = [4, 5, 6, 8, 9];

console.log(findMedian(arr1,arr2));时间复杂度

因为二分查找的时间复杂度O（logn），所以是O（log（n+m））；

ps还有一种切割数组的方式：https://zhuanlan.zhihu.com/p/30010442