給定兩個大小為 m 和 n 的正序（從小到大）數(shù)組 nums1 和 nums2缩宜。
請你找出這兩個正序數(shù)組的中位數(shù)，并且要求算法的時間復(fù)雜度為 O(log(m + n))廓推。
你可以假設(shè) nums1 和 nums2 不會同時為空刷袍。
示例 1:
nums1 = [1, 3]
nums2 = [2]
則中位數(shù)是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
則中位數(shù)是 (2 + 3)/2 = 2.5
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
var n = nums1.length;
var m = nums2.length;
var left = Math.floor((n + m + 1) / 2)
var right = Math.floor((n + m + 2) / 2)
return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
};
var getKth = function(nums1, start1, end1, nums2, start2, end2, k) {
var len1 = end1 - start1 + 1;
var len2 = end2 - start2 + 1;
//讓 len1 的長度小于 len2，這樣就能保證如果有數(shù)組空了樊展，一定是 len1
if (len1 > len2) {
return getKth(nums2, start2, end2, nums1, start1, end1, k);
}
if (len1 == 0) {
return nums2[start2 + k - 1];
}
if (k == 1){
return Math.min(nums1[start1], nums2[start2]);
}
var i = start1 + Math.min(len1, Math.floor(k / 2)) - 1;
var j = start2 + Math.min(len2, Math.floor(k / 2)) - 1;
if (nums1[i] > nums2[j]) {
return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
}
else {
return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
}
}
思路：
轉(zhuǎn)化一下思路呻纹，找中位數(shù)也就是找合并后數(shù)組的第K個最小數(shù)，K為數(shù)組的長度的一半
————————
想要學(xué)習(xí)Cocos的同學(xué)专缠，歡迎關(guān)注我的零基礎(chǔ)Cocos教程
https://ke.qq.com/course/313749
