關於JavaScript求解兩個有序列表的中值問題的範例程式碼

將一個序列內的數由小到大排列，此時位於中間位置的變數值稱為中值。

那麼，已知兩個有序列表，如何求它們共同的中位數？

拿到這個問題，你首先想到的解決方法一定是，把兩個有序列表合併，然後統一做增序排序，最後一次性取出中位數。

這樣的做法，很簡單方便，但效率並不高，因為排序的緣故，所以是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求解兩個有序列表的中值問題的範例程式碼的詳細內容。更多資訊請關注PHP中文網其他相關文章！