欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  web前端

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

程序员文章站 2022-03-10 17:24:56
...
将一个序列内的数由小到大排列,此时位于中间位置的变量值称之为中值。

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

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

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

那么,怎么进行优化呢?

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

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++;
    }
};

以上就是关于JavaScript求解两个有序列表的中值问题的示例代码的详细内容,更多请关注其它相关文章!