关于JavaScript求解两个有序列表的中值问题的示例代码

将一个序列内的数由小到大排列，此时位于中间位置的变量值称之为中值。

那么，已知两个有序列表，如何求它们共同的中值？

拿到这个问题，你首先想到的解决方法肯定是，把两个有序列表合并，然后统一做增序排序，最后一次性取出中值。

这样的做法，很简单方便，但效率并不高，因为排序的缘故，所以是O(N*logN)的算法。

那么，怎么进行优化呢？

立即学习“Java免费学习笔记（深入）”；

可以参考有序线性表合并的算法：

Anyword

AI文案写作助手和文本生成器，具有可预测结果的文案 AI

下载

1.用两个指针分别指向当前的有序列表，用一个新数组来接收比较过的较小数组元素。

2.比较两个指针指向的数组元素，将较小的存入新数组，该指针后移。这个过程将持续到，指针中某一个为空，或者中值已经被新数组接收，那么就直接返回中值。

3.如果阶段2完成后，有指针非空，而且此时中值并没有被新数组接收，那么，继续用该指针遍历有序列表，直到接收到中值，将其返回。

4.经过优化后的算法是O(m+n)的，效率很大地提高了。

var findMedianSortedArrays = function(nums1, nums2) {
	//两个列表的总元素个数
    var totalLength = nums1.length + nums2.length;
	//总元素个数是否为奇数
    var isOdd = totalLength % 2 === 0 ? false : true;
	//两个指针
    var p1 = 0;
    var p2 = 0;
	//用于接收的新数组
    var array = [];
	//只要指针仍然在范围内
    while(p1 < nums1.length && p2 < nums2.length){
		//将较小的元素压入新数组，指针后移
        if(nums1[p1] < nums2[p2]){
            array.push(nums1[p1]);
            p1++;
        }
        else{
            array.push(nums2[p2]);
            p2++;
        }
		//如果此时已接收中值,弹出中值，返回
        if(array.length === totalLength / 2 + 1){
            return (array.pop() + array.pop()) / 2;
        }
        if(isOdd && array.length === Math.ceil(totalLength / 2)){
            return array.pop();
        }
    }
	//有一个指针已经出界了
	//此时仍然没有接收到中值
	//对另一个指针继续遍历
	//直到接收中值,弹出中值，并返回
    while(p1 < nums1.length){
        array.push(nums1[p1]);
        if(array.length === totalLength / 2 + 1){
            return (array.pop() + array.pop()) / 2;
        }
        if(isOdd && array.length === Math.ceil(totalLength / 2)){
            return array.pop();
        }
        p1++;
    }
    while(p2 < nums2.length){
        array.push(nums2[p2]);
        if(array.length === totalLength / 2 + 1){
            return (array.pop() + array.pop()) / 2;
        }
        if(isOdd && array.length === Math.ceil(totalLength / 2)){
            return array.pop();
        }
        p2++;
    }
};