6.LeetCode-寻找两个正序数组的中位数-4题 (javascript)

题目：

解题1:

来暴力一波，再慢慢优化

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    let i = 0;
    let j = 0;
    let list = [];
    let m = 0;
    while (i<nums1.length || j<nums2.length) {
        if (i == nums1.length) {
            list.push(nums2[j]);
            j++;
        } else if ( j == nums2.length) {
            list.push(nums1[i]);
            i++;
        } else if (nums1[i] > nums2[j]) {
            list.push(nums2[j]);
            j++;
        } else {
            list.push(nums1[i]);
            i++;
        }
    }
    if (list.length % 2 == 0) {
        m = (list[(list.length-2)/2] + list[(list.length)/2])/2;
    } else {
        m = list[(list.length-1)/2];
    }
    return m;
};

• 时间和空间都超过5%的人左右，哎，需要好好优化一下。
• 切记，不要混在一起暴力排序，有复杂度要求。
• 好的是，这是两个有序数组，且 均为升序，所以可以巧妙的去遍历，构建新的有序数组。只需要遍历一次。
• 还可以从代码逻辑合并 与 空间消耗方面进行优化。

解题2: 优化-合并一下判断逻辑

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

• 优化后，时间效率击败80%，空间耗损击败70%。
• emm，想想还能不能继续优化。

解题3:优化-减少一下空间消耗

• 时间击败40-90%，空间击败85%+。
• 没有上一个版本速度快，虽然遍历减少了，但是判断变多了。
• 也许，可以继续优化？
• 以后再说吧哈哈

var findMedianSortedArrays = function(nums1, nums2) {
    let i = 0;
    let j = 0;
    let l = nums1.length + nums2.length;
    let k = 0;
    let l2 = [];
    while (i<nums1.length || j<nums2.length) {
        if (k>l/2) {
            break;
        }
        if (i == nums1.length || nums1[i] > nums2[j]) {
            if (k >= l/2-1 && k<= l/2) {
                l2.push(nums2[j]);
            }
            j++;
            k++;
        } else {
            if (k >= l/2-1 && k<= l/2) {
                l2.push(nums1[i]);
            }
            i++;
            k++;
        }
    }
    if (l2.length % 2 == 0) {
        return (l2[0] + l2[1])/2;
    } else {
        return l2[0]
    }
};

• 这次优化的思路：
• 遍历合并有序列表形成新有序列表的思路不变。
• 因为是取中位数，所以我们可以不用全部遍历完，只需要遍历到总长度/2就够了，非单即双，我们所需要的只是中间那1或2个数。
• 因此，不需要构建完整连续的新列表，只需要把最重要的中间那1-2个数保存进去就行。
• 这样就实现了空间消耗的减少。只遍历一半长度，且没有过多增加额外空间开销，不过判断有点多。