js有序数组的连接问题
1.前言
昨天碰到一道关于如何解决有序数组的连接问题，这是一个很常见的问题。但是这里要考虑到代码的效率问题，因为要连接的数组都是有序的，这是一个非常重要的前提条件。
2.简单但效率不高的算法
我首先想到的是使用内置的concat方法，然后再对其进行排序，这种方法完全没有考虑到数组是有序的前提条件，代码如下：
代码如下:
function concatSort(arrA,arrB){
return arrA.concat(arrB).sort();
}为了弄清楚sort排序到底使用的是什么算法，特地到看了V8引擎的算法（连接），大概意思是当数组的长度较短的时候使用的是插入排序（InsertionSort），当数组的长度较长的时候使用的是快速排序（QuickSort）。纠正了自己长时间来的一个误区，一直以为sort使用的是冒泡。
3. 取小值插入的方法
大概思路：就是同时对两个数组进行遍历，设置两个标志（i，j）用于记录遍历的位置，将两个数组中较小的那个值插入新数组中，接着再将标志往前移动一个位置，重复比较，直到搜索值都插入到数组中。第一次做的时候判断条件写错了，所以出现了死循环，暴露了自己算法能力还是挺薄弱的。
代码如下:
function con(arrA,arrB){
var i , j , k, lenA = arrA.length, lenB = arrB.length , allLen = lenA + lenB,result = [];
for(i=0,j=0,k =0; k < allLen; k++ ){
if(i < lenA &&(j >= lenB || arrA[i] < arrB[j])){
result.push(arrA[i++]);
}else{
result.push(arrB[j++]);
}
}
return result;
}
var a = [1,2,4], b = [3,5,6,7,10];
console.log(con(a,b)); //[1,2,3,4,5,6,7,10] 将这个算法与上面的方法1，在jsperf进行性能对比，发现第二种算法的效率明显优于第一种。不相信就猛击这里。
4.问题升级：增加合并数组的数量
假如增加数组的个数，；例如 A = [1,5],B = [2,6],C = [3,4].......K = [....]，求合并的数组。
当时被问到这个问题，第一感觉就是很像”归并算法“，但是又一想使用归并算法是用不上数组有序这个前提条件的。接着又想到了堆排序、快排序等算法，发现就是无法很有效地用上数组有序这个前提条件，最后选择放弃。面试完后依然没有思路，想了好久不知道如何高效的解决这个问题。快回宿舍的时候，师弟说了一句”又要过节了“，”又“字点醒了我，代码如下：
代码如下:
function conMore(){
var outerArr = [], i ,len = arguments.length , result = [];
for(i = 0 ; i<len; i++){
outerArr.push(arguments[i]);
}
if(result.length === 0){
result = outerArr[0];
}
for(i=1 ;i< len; i++){
result = con(result,outerArr[i]);
}
return result;
}
function con(arrA,arrB){
var i , j , k, lenA = arrA.length, lenB = arrB.length , allLen = lenA + lenB,result = [];
for(i=0,j=0,k =0; k < allLen; k++ ){
if(i < lenA &&(j >= lenB || arrA[i] < arrB[j])){
result.push(arrA[i++]);
}else{
result.push(arrB[j++]);
}
}
return result;
}
var a = [1,4,7], b = [2,5,8], c = [3,6,9,10];
console.log(conMore(a,b,c)); //[1,2,3,4,5,6,7,8,9,10]再次使用jsperf对代码的性能进行测试分析，结果请猛击这里.
相关文章
- 在php中eval是一个函数并且不能直接禁用了，但eval函数又相当的危险了经常会出现一些问题了，今天我们就一起来看看eval函数对数组的操作 例子， <?php $data="array...2016-11-25
- 这篇文章主要介绍了Python 图片转数组,二进制互转操作，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-09
- 本文章提供在量的数据中级操作实例有如对键名比较计算数组的差集 计算差集 给指定数组中插入一个元素 反转数组 交集赋值新的数组实例。 //定义回调函数 funct...2016-11-25
- 这篇文章主要介绍了C#二维数组基本用法,以实例形式分析了C#中二维数组的定义、初始化、遍历及打印等用法,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
- Array数组在C#中同样是最基本的数据结构,下面为大家C#数组的常用操作方法小结,皆为细小的代码段,欢迎收看收藏...2020-06-25
- 下面一段代码给大家介绍php curl模拟post请求的示例代码，具体代码如下： <?php$uri = "http://www.cnblogs.com/test.php";//这里换成自己的服务器的地址// 参数数组$data = array ( 'name' => 'tanteng'// 'passwor...2015-11-24
PHP传值到不同页面的三种常见方式及php和html之间传值问题
在项目开发中经常见到不同页面之间传值在web工作中，本篇文章给大家列出了三种常见的方式。接触PHP也有几个月了，本文总结一下这段日子中，在编程过程里常用的3种不同页面传值方法，希望可以给大家参考。有什么意见也希望大...2015-11-24- js修改input的type属性有些限制。当input元素还未插入文档流之前，是可以修改它的值的，在ie和ff下都没问题。但如果input已经存在于页面，其type属性在ie下就成了只读属性了，不可以修改。...2013-10-19
- 1，utf8_bin跟utf8_general_ci的区别 ci是 case insensitive, 即 "大小写不敏感", a 和 A 会在字符判断中会被当做一样的; bin 是二进制, a 和 A 会别区别对待. 例如你运行: SELECT * FROM table WHERE txt = 'a'...2013-10-04
- 下面小编就为大家带来一篇C# 拷贝数组的几种方法(总结)。小编觉得挺不错的，现在就分享给大家，也给大家做个参考。一起跟随小编过来看看吧...2020-06-25
- 本文记录的要实现的功能类似于 MySQL 中的 ORDER BY，上个项目中有遇到这样的一个需求。 要求：从两个不同的表中获取各自的4条数据，然后整合(array_merge)成一个数组，再根据数据的创建时间降序排序取前4条。 遇到这个...2014-06-07
- 一、1 CREATE TABLE NAME(name VARCHAR(10)); 对这个表，缺省情况下，下面两个查询的结果是一样的：复制代码 代码如下: SELECT * FROM TABLE NAME WHERE name='clip'; SELECT * FROM TABLE NAME WH...2015-03-15
- 这篇文章主要介绍了C#实现字符串转换成字节数组的简单实现方法,仅一行代码即可搞定,非常简单实用,需要的朋友可以参考下...2020-06-25
- 一.mysql默认不支持中文,它的server和db默认是latin1编码.所以我们要将其改变为utf-8编码,因为utf-8包含了地球上大部分语言的二进制编码 1.关闭mysql服务 sudo /etc/init.d/mysql stop 2.修改mysql配置文件 mysql配...2015-10-21
- 这篇文章主要介绍了c#将字节数组转成易读的字符串的实现，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-06-25
- 这篇文章主要介绍了C#读取文件所有行到数组的方法,涉及C#针对文件及数组的相关操作技巧,需要的朋友可以参考下...2020-06-25
- 如何将下面的二维数组转为一维数组。复制代码 代码如下:$msg = array( array( 'id'=>'45', 'name'=>'jack' ), array( 'id'=>'34', 'name'=>'mary' ), array( 'id...2014-05-31
- 在php中为我们提供了一个函数var_export 他可以直接将php代码入到一个文件中哦。 代码如下 复制代码 var_export($times,true);后面不加tru...2016-11-25
- 本文为代码分享，也是在工作中看到一些“大牛”的代码，做做分享。 具体是这样的，如下一个二维数组，是从库中读取出来的。 代码清单： 复制代码 代码如下: $user = array( 0 => array( 'id' => 1, 'name' => '张三', 'ema...2014-06-07
- 1.前言 昨天碰到一道关于如何解决有序数组的连接问题，这是一个很常见的问题。但是这里要考虑到代码的效率问题，因为要连接的数组都是有序的，这是一个非常重要的前提条件。2.简单但效率不高的算法 我首先想到的是使用...2013-10-04