Sample code for solving the median problem of two ordered lists using JavaScript

Arrange the numbers in a sequence from small to large. At this time, the variable value located in the middle is called the median value.

So, given two ordered lists, how to find their common median?

When you get this problem, the first solution you think of is to merge the two ordered lists, then sort them in ascending order, and finally take out the median value at once.

This approach is very simple and convenient, but it is not very efficient. Because of the sorting, it is an algorithm of O(N*logN).

So, how to optimize?

You can refer to the algorithm for merging ordered linear lists:

1. Use two pointers to point to the current ordered list, and use a new array to receive the comparison of smaller array elements.

2. Compare the array elements pointed to by the two pointers, store the smaller one in the new array, and move the pointer backward. This process will continue until one of the pointers is empty, or the median value has been received by the new array, then the median value will be returned directly.

3.If after phase 2 is completed, a pointer is non-null, and the middle value is not received by the new array at this time, then continue to use the pointer to traverse the ordered list , until the median value is received, return it.

4.The optimized algorithm is O(m+n), and the efficiency is greatly improved.

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

The above is the detailed content of Sample code for solving the median problem of two ordered lists using JavaScript. For more information, please follow other related articles on the PHP Chinese website!