4.Median of Two Sorted Arrays

题目描述

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

JS解法

解法一：合并两个数组，并查找中位数 —— O(m + n)
如果使用concat + sort，则是O(nlogn)

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    // merge and find median
    let num = [];
    let index1 = 0;
    let index2 = 0;
    while (index1 < nums1.length && index2 < nums2.length) {
        if (nums1[index1] < nums2[index2]) {
            num.push(nums1[index1++]);
        } else {
            num.push(nums2[index2++]);
        }
    }
    if (index1 < nums1.length) {
        num = num.concat(nums1.slice(index1));
    }
    if (index2 < nums2.length) {
        num = num.concat(nums2.slice(index2));
    }
    let length = num.length;
    if (length % 2 === 1) {
        return num[parseInt((length - 1) / 2)];
    } else {
        return (num[parseInt((length - 1) / 2)] + num[parseInt((length) / 2)]) / 2;
    }
}

未完待续