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 if(i = lenB || arrA[i] 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
}
if(result.length === 0){
result = outerArr[0];
}
for(i=1 ;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 if(i = lenB || arrA[i] 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对代码的性能进行测试分析,结果请猛击这里.

win11无法连接局域网打印机怎么办?有不少用户的win11系统在使用局域网打印机功能的时候,无法正常连接到共享打印机,出现这个问题,可能是连接步骤或者是某项功能服务没打开。今天小编就给大家带来了多种解决方法,很多小伙伴不知道怎么详细操作,小编下面整理了win11电脑不能连共享打印机解决技巧,如果你感兴趣的话,跟着小编一起往下看看吧!win11电脑不能连共享打印机解决技巧1、首先,按键盘上的Win+X组合键,或右键点击任务栏上的Windows开始图标,在打开的隐藏菜单项中,选择运行;2、运行窗口

MariaDB是一种开源的关系型数据库管理系统,它是MySQL的一个分支。PHP作为一种开源的服务器端脚本语言,被广泛应用于Web开发中。在很多Web开发项目中,需要使用PHP连接到MariaDB数据库,以便在Web应用程序中存储和检索数据。这篇文章将介绍如何使用PHP编写代码来连接MariaDB数据库。一、安装MariaDB服务器在使用PHP连接Maria

MySQL连接错误1203,如何解决?MySQL是一种广泛使用的关系型数据库管理系统,但是在使用MySQL时,一些连接错误可能会出现。其中一个常见的错误是错误代码1203,它表示数据库连接已中断。在遇到这个错误时,可以采取一些措施来解决问题。首先,我们需要确定错误1203的确切原因。这个错误通常是由于连接超时或连接过多引起的。连接超时可能是由于数据库服务器负

随着现代程序开发的不断发展,软件项目往往需要同时使用多个任务库来处理不同的任务。PHP语言一直是Web开发的重要工具,其在7.0版本中引入了新的并发处理特性,使得PHP在处理任务库时更加高效、灵活。在8.0版本中,PHP又新增了对连接多个任务库的支持,这为我们在处理大量数据和并发请求时提供了极大的便利。在本文中,我们将探讨PHP8.0中连接多个任务库的方法和

Python连接阿里云接口,实现邮件发送功能阿里云提供了一系列的服务接口,其中包括了邮件发送服务。通过Python脚本连接阿里云接口,我们可以实现邮件的快速发送。本篇文章将向您展示如何使用Python脚本连接阿里云接口,并实现邮件发送功能。首先,我们需要在阿里云上申请邮件发送服务,获取相应的接口信息。在阿里云管理控制台中,选择邮件推送服务,然后创建一个新的邮

MySQL连接错误2059,该如何解决?在使用MySQL数据库时,有时会遇到连接错误2059的问题。这个错误通常是由于MySQL服务器与客户端之间的连接问题引起的。在本文中,我将解释导致此错误的一些常见原因,并提供一些可能的解决方案。防火墙问题:在一些情况下,防火墙设置可能会阻止MySQL服务器与客户端之间的通信。这种情况下,你需要检查防火墙设置并确保MyS

如何在Java程序中优化MySQL连接的写入性能和并发性能?在开发Java程序时,我们经常需要使用到数据库,而MySQL作为一种常见的数据库管理系统,其连接的写入性能和并发性能是我们需要关注的重点。本文将介绍如何在Java程序中优化MySQL连接的写入性能和并发性能,以提升程序的效率。使用连接池管理连接:连接池可以管理数据库连接的创建、销毁和复用,避免频繁地

Java连接数据库的SQLException异常常见原因是什么?在Java开发中,Database操作是非常关键的一环。其中,对于常用的CRUD操作,特别是SELECT和INSERT操作,都需要使用到JDBC来实现。但是,在JDBC应用开发中,与数据库的连接操作、SQL语言的执行过程、以及结果集的处理等阶段,可能会发生SQLException异常。本文将分析


热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

SublimeText3 Mac版
神级代码编辑软件(SublimeText3)

适用于 Eclipse 的 SAP NetWeaver 服务器适配器
将Eclipse与SAP NetWeaver应用服务器集成。

MinGW - 适用于 Windows 的极简 GNU
这个项目正在迁移到osdn.net/projects/mingw的过程中,你可以继续在那里关注我们。MinGW:GNU编译器集合(GCC)的本地Windows移植版本,可自由分发的导入库和用于构建本地Windows应用程序的头文件;包括对MSVC运行时的扩展,以支持C99功能。MinGW的所有软件都可以在64位Windows平台上运行。

Dreamweaver CS6
视觉化网页开发工具

WebStorm Mac版
好用的JavaScript开发工具