寻找两个正序数组的中位数[困难][二分查找]

标题 4. 寻觅两个正序数组的中位数 – 力扣（LeetCode） (leetcode-cn.com)

解法1

时刻复杂度O(m+n),需求遍历(m+n)/2次

空间复杂度O(1),只需求声明几个常数变量

思路

当两个数组一共的数字个数为偶数的时分，需求取得下标为(m+n-1)/2 和 (m+n)/2方位的数字，然后得到平均值;当两个数组一共的数字个数为奇数的时分,(m+n-1)/2 和 (m+n)/2的成果一样，是在相同的方位。

因而从头开始遍历两个数组，经过index_1 和 index_2来记载下标，每次挑选小的数字去右移，index表明一共移动的间隔，假如index为(m+n-1)/2 或者是(m+n)/2的方位的时分，就记载当时方位的值。

代码：

var findMedianSortedArrays = function(nums1, nums2) {
    let index = -1, index_1 = 0, index_2 = 0, tmp = 0;
    let target1 = Math.floor((nums1.length + nums2.length - 1)/2);
    let target2 = Math.floor((nums1.length + nums2.length)/2);
    let num = [0, 0];
    let len1 = nums1.length, len2 = nums2.length;
    while(index_1 < len1 || index_2 < len2){
        if(index_1 < len1 && index_2 < len2){
            tmp = nums1[index_1] <= nums2[index_2]? nums1[index_1++]: nums2[index_2++];        
        }else if(index_1 < len1){
            tmp = nums1[index_1++];
        }else{
            tmp = nums2[index_2++];
        }
        index++;
        if(index == target1){
            num[0] = tmp;
        }
        if(index == target2){
            num[1] = tmp;
            break;
        }
    }
    return (num[0]+num[1])/2;
};

解法2

时刻复杂度为O(m+n)的解法不难想到，但是标题要求时刻复杂度为O(log(m+n))，意味着单纯的从头遍历无法满足时刻复杂度的要求，从log(m+n)的复杂度出发，能够想到是经过二分法来进行查找。

基本思路

假设一共是m+n个数字, 寻觅中位数, k = (m+n)/2, 即需求找到第k小的数字,。

在O(m+n)的算法中, 每次遍历都是去掉k之前的1个数字；经过二分法的设计，能够完成在每次遍历前都去掉k之前的k/2个数字，因而能够完成log等级的时刻复杂度。

因而取得两个数组的k/2方位的数字，来比较大小, 小的数字及其前面的数字, 能够必定, 他们能够被去掉。然后取得了新的数组长度 = k – 2/k, 将k设置为这个新的长度,然后进行递归调用。

var findMedianSortedArrays = function(nums1, nums2) {
    let n = nums1.length;
    let m = nums2.length;
    let left = Math.floor((n+m+1)/2), right = Math.floor((n+m+2)/2);
    // 获取nums1 和 nums2 的第left个
    return (getKth(nums1, 0, n-1, nums2, 0, m-1, left) + getKth(nums1, 0, n-1, nums2, 0, m-1, right))/2;
};
let getKth = (nums1, start1, end1, nums2, start2, end2, k)=>{
    let len1 = end1 - start1 + 1;  // nums1的长度
    let len2 = end2 - start2 + 1;  // nums2的长度
    // 第一个数组是短的
    if(len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
    if(len1 == 0) return nums2[start2 + k - 1];
    // 假如第一个数组的长度是0，直接回来第二个数组的长度
    if(k == 1) return Math.min(nums1[start1], nums2[start2]);
    // 假如长度是1, 就直接回来两个数组里面的最小数字
    let i = start1 + Math.min(len1, Math.floor(k/2)) - 1; 
    let j = start2 + Math.min(len2, Math.floor(k/2)) - 1;
    // 获取k/2的方位
    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));
    }
}