leecode-4.Median of Two Sorted Arrays

找出两个数组的中位数

1.题目描述：

（1）给定两个已经排好序的数组。
（2）复杂度是O(log (m+n))。
（3）两个数组不会同时为空。

2.算法分析：

逐点分析，取中位数的条件是知道数组的长度，即为两个数组长度的和，又要有一个必要条件是数组是有顺序的，所以第一步合并两个给出的数组为一个有序的数组。
合并的细节是，不是传统的两层for循环，而是给两个数组两个指针，同时遍历比较，每次都取最小的放入新数组，同时也注意，当指针超过某个数组后，就不再比较，只从另一个读取插入。这样的遍历利用了题目的有序数组条件，也满足复杂度要求。

3.算法实现：

var findMedianSortedArrays = function(nums1, nums2) {
    var i=0,j=0,carr=[];
    while(i<nums1.length||j<nums2.length){
        if(nums1[i]>nums2[j]||i>=nums1.length){
            carr.push(nums2[j]);
            j++;
        }
        else if(nums2[j]>nums1[i]||j>=nums2.length){
            carr.push(nums1[i]);
            i++;
        }
        else{
            carr.push(nums1[i]);carr.push(nums2[j]);
            i++;j++;
        }
    }
    return carr.length%2==0 ? (carr[carr.length/2]+carr[carr.length/2-1])/2 : carr[Math.floor(carr.length/2)];
};

赏

感谢您的支持，加个好友吧

微信