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

来源：懂视网责编：小采时间：2020-11-27 20:23:55

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

关于JavaScript求解两个有序列表的中值问题的示例代码:将一个序列内的数由小到大排列，此时位于中间位置的变量值称之为中值。那么，已知两个有序列表，如何求它们共同的中值？拿到这个问题，你首先想到的解决方法肯定是，把两个有序列表合并，然后统一做增序排序，最后一次性取出中值。这样的做法，很简单方便，但

推荐度：

点击下载本文 文档为doc格式

导读关于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求解两个有序列表的中值问题的示例代码

推荐度：

点击下载本文 文档为doc格式

标签： js 代码问题

热门焦点

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

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

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

最新推荐

猜你喜欢

热门推荐