题目内容

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

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

则中位数是 2.0

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

则中位数是 (2 + 3)/2 = 2.5

解法一，我的解法

虽然是hard类别的，但思路还是很清晰。看完题目后可以很容易想到的思路是：将两个数组合并后排序再计算中位数就好了。

我的代码也是这样实现的:

var findMedianSortedArrays = function(nums1, nums2) {
    // 两个数组合并后并排序
    // 需要考虑数组为纯负值的情况，会导致排序出错
    let tempArr = (nums1.concat(nums2)).sort((a, b) => {return a - b})
    if (tempArr.length % 2 === 1) {
        // 奇数项返回中间那个
        return tempArr[Math.floor(tempArr.length / 2)]
    } else {
        let index = tempArr.length / 2
        return (tempArr[index - 1] + tempArr[index]) / 2
    }
};

不过踩了个坑，JavaScript中数组的sort默认排序规则是在将元素转换为字符串，然后比较它们的UTF-16代码单元值序列。

所以这就导致-2要比-1大，导致排序出错。解决办法也很简单，自行定义sort方法中的排序规则而不是使用默认的。

解法二，双指针扫描

主要逻辑是确定中位数的位置，然后两个数字间用指针互相比较大小然后挪到中位数的位置，就知道中位数是多少了。