关于javascript:寻找两个正序数组的中位数

33次阅读

共计 1974 个字符,预计需要花费 5 分钟才能阅读完成。

一、归并排序办法实现

// 工夫复杂度 O(m+n), 空间复杂度 O(m+n)
var findMedianSortedArrays = function(nums1, nums2) {let nums = [], m = nums1.length, n = nums2.length;
    if(m === 0) {   //nums1 为空数组
        if(n % 2 === 0) {   //nums2 的长度为偶数
            return (nums2[n/2 - 1] + nums2[n/2])/2;
        } else {return nums2[Math.floor(n/2)];
        }
    }

    if(n === 0) {   //nums2 为空数组
        if(m % 2 === 0) {   //nums1 的长度为偶数
            return (nums1[m/2 - 1] + nums1[m/2])/2;
        } else {return nums1[Math.floor(m/2)];
        }
    }

    let count = 0, i = 0, j = 0;        //count 代表合并后的数组的长度, i, j 别离代表遍历 nums1, nums2 的索引
    while(count !== (m + n)) {if(i === m) {       //nums1 曾经遍历实现
            while(j !== n) {nums[count++] = nums2[j++];
            }
            break;
        }

        if(j === n) {       //nums2 曾经遍历完
            while(i !== m) {nums[count++] = nums1[i++];
            }
            break;
        }

        // 这样能够保障合并后的数组是有序的
        if(nums1[i] < nums2[j]) {nums[count++] = nums1[i++];
        } else {nums[count++] = nums2[j++];
        }
    }

    if(count % 2 === 0) {       // 合并后的数组的元素个数是偶数
        return (nums[count/2 - 1] + nums[count/2])/2;
    } else {return nums[Math.floor(count/2)];
    }
};

console.log(findMedianSortedArrays([0, 1, 2, 2, 3], [3, 4, 5]));

二、数组连贯后排序实现

// 工夫复杂度 O(m+n), 空间复杂度 O(m+n)
var findMedianSortedArrays = function(nums1, nums2) {
    let length1 = nums1.length;
    let length2 = nums2.length;
    let middle = (length1 + length2 - 1)/2;
    var nums = nums1.concat(nums2).sort();
    if(Math.floor(middle) === middle) {     // 如果 middle 是一个整数
        return nums[middle];
    } else {        // 如果 middle 不是一个整数
        return (nums[Math.floor(middle)] + nums[Math.ceil(middle)])/2;
    }
};

console.log(findMedianSortedArrays([0, 1, 2, 2, 3], [3, 4, 5]));

三、双指针法实现

// 工夫复杂度 O(m+n), 空间复杂度 O(1)
/**
 * 双指针法:如果两个数组的和为偶数的话,则需遍历 len/2 + 1 次,如果为奇数,则需遍历 Math.floor(len/2) + 1 次,* 应用 prev 和 current 来别离记录上一轮循环和该轮循环的值
 * @param {Array} nums1 
 * @param {Array} nums2 
 */
var findMedianSortedArrays = function(nums1, nums2) {
    let m = nums1.length, n = nums2.length, len = m + n;
    let prev = -1, current = -1, aStart = 0, bStart = 0;    //prev 保留上一轮循环的后果,current 保留以后循环的后果,aStart 示意 nums1 的指针,bStart 示意 nums2 的指针 
    for(let i = 0; i <= len/2; i++) {
        prev = current;         //prev 指向上一轮循环的值
        //nums1 指针向后移的条件:aStart < m 且 nums1[aStart] < nums2[bStart],然而第二个条件的前提条件是 nums2 的指针不能越界
        if(aStart < m && (bStart >= n || nums1[aStart] < nums2[bStart])) {current = nums1[aStart++];
        } else {current = nums2[bStart++];
        }
    }

    if(len % 2 === 0) {return (prev + current)/2;
    } else {return current;}
};

console.log(findMedianSortedArrays([0, 1, 2, 3], [3, 4, 5]));

正文完
 0