# 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思路首先

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));时间复杂度

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

• 发表于:
• 原文链接：http://kuaibao.qq.com/s/20180328G1V05Q00?refer=cp_1026
• 腾讯「云+社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。

2018-07-02

2018-06-27

2018-05-08

2019-09-22

2019-09-22

2019-09-22