4.寻找两个正序数组的中位数

题目地址

解题思路

该题要求两个正序数组中的中位数，首先要将两个数组合并并排序。这就涉及到对数组排序的问题。对于数组长度为奇数的情况下，中位数就是数组中间的那个数，对于长度为偶数的数组，中位数就是中间两个数的平均数

代码

var findMedianSortedArrays = function(nums1, nums2) {
    const result = [...nums1,...nums2];
    const len = result.length;
    result.sort((a,b)=> a - b);
    let idx = 0;
    if(len % 2 !== 0){
        idx = (len - 1)/2
        return result[idx].toFixed(5)
    }else{
        idx = len / 2;
        return ((result[idx-1] + result[idx])/2).toFixed(5)
    }   
};
const nums1 = [1,2],nums2 = [3,4]
console.log(findMedianSortedArrays(nums1,nums2));

主要应用了Array.sort()对数组进行排序，其实题目有个要求：算法的时间复杂度应该为 O(log (m+n)) 。且没有利用到数组有序这一特点。

优化

解题思路一：
合并数组并进行排序，时间复杂度最快为O((m+n)log(m+n))

解题思路二：参考leetcode第88题，利用快慢指针进行排序

解题思路三：二分查找

【未完待续，先学习快慢指针进行排序】