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对代码的性能进行测试分析，结果请猛击这里.

赞 (0)

相关推荐

  • php判断一个数组是否为有序的方法

    本文实例讲述了php判断一个数组是否为有序的方法.分享给大家供大家参考.具体分析如下: 这段代码的时间复杂度为O(n) <?php function JudegSortArray($array) { if ($array [0] > $array [1]) { $flag = 1; } else { $flag = 0; } $temp = $flag; $len = count ( $array ); for($i = 1; $i < $len; $i ++) { if ($flag

  • Python实现二维有序数组查找的方法

    本文实例讲述了Python实现二维有序数组查找的方法.分享给大家供大家参考,具体如下: 题目:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序.请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数. 这题目属于比较简单但又很不容易想到的,问了两个同学,大家一时都没有想出来怎么解决比较快.第一反应都是二分查找.对于每一行进行二分查找,然后查找过程可以把某些列排除掉,这是大家都能想到的基本的思路. 比较好的另一种思路是,首先选取数组右上角

  • java实现向有序数组中插入一个元素实例

    整理文档,搜刮出一个java实现向有序数组中插入一个元素,稍微整理精简一下做下分享 package cn.jbit.array; import java.util.*; public class Insert { public static void main(String[] args) { //字符排序 char[] chars = new char[9]; chars[0] = 'a'; chars[1] = 'c'; chars[2] = 'u'; chars[3] = 'b'; cha

  • 归并算法之有序数组合并算法实现

    归并算法之有序数组合并算法实现 一个简单的有序数组合并算法:写一个函数,传入 2 个有序的整数数组,返回一个有序的整数数组.实现相当简单,创建一个长度为这两个长度之和的数组,然后分别用三个指针指向这三个数组,找到这两个数组中各个元素在合并数组中的位置并插入,直到某个数组指针到达尾部.再将另一个数组剩下的所有元素,直接放入归并数组尾部.算法的简单实现,需要注意的是对参数的校验,判断数组是否有序. public class MergeOrderedArray { public static int[

  • javascript 折半查找字符在数组中的位置(有序列表)

    复制代码 代码如下: /** * 折半查找字符在数组中的位置(有序列表) * @param array 被检索的数组 * @param x 要查找的字符 * @type int * @returns 字符在数组中的位置,没找到返回-1 */ function binarySearch(array,x){ var lowPoint=1; var higPoint=array.length; var returnValue=-1; var midPoint; var found=false; whi

  • 合并有序数组的实现（java与C语言）

    合并有序数组的实现 java版本: 实例代码 public class Merge { //合并有序数组 public static void mergeSort(int a[], int b[], int c[]) { int n = a.length, m = b.length; int i, j, k; i = j = k = 0; while (i < n && j < m) { if (a[i] < b[j]) { c[k++] = a[i++]; } else

  • php实现有序数组打印或排序的方法【附Python、C及Go语言实现代码】

    本文实例讲述了php实现有序数组打印或排序的方法.分享给大家供大家参考,具体如下: 有序的数组打印或排序对于php来讲非常的简单了这里整理了几个不同语言的做法的实现代码,具体的我们一起来看这篇php中有序的数组打印或排序的例子吧. 最近有个面试题挺火的--把2个有序的数组打印或排序,刚看到这个题的时候也有点蒙,最优的算法肯定要用到有序的特性. 思考了一会发现也不是很难,假如数组是正序排列的,可以同时遍历2个数组,将小的值进行排序,最后会遍历完一个数组,留下一个非空数组,而且剩下的值肯定大于等于已

  • 用递归查找有序二维数组的方法详解

    假设给定一个有序二维数组,每一行都是从左到右递增,每一列都是从上到下递增,如何完成一个函数,输入这样一个二维数组和一个整数,判断这个整数是否在这个二维数组中.假设一个4×4的有序二维数组:          1          2          8          9          2          4          9          12          4          7          10        13          6          8 

  • C语言实现在数组A上有序合并数组B的方法

    本文实例讲述了C语言实现在数组A上有序合并数组B的方法,分享给大家供大家参考.具体分析如下: 题目:数组A和数组B均有序,数组A有足够大内存来容纳数组B,将数组B有序合并到数组A中 分析:如果由前至后合并,复杂度将会是O(N2),这样的复杂度显然不是最优解,利用两个指针指向两个数组的尾部,从后往前遍历,这样的复杂度为O(n2) 由此可以写出下面的代码: #include <iostream> #include <algorithm> #include <iterator>

  • js有序数组的连接问题

    1.前言 昨天碰到一道关于如何解决有序数组的连接问题,这是一个很常见的问题.但是这里要考虑到代码的效率问题,因为要连接的数组都是有序的,这是一个非常重要的前提条件. 2.简单但效率不高的算法 我首先想到的是使用内置的concat方法,然后再对其进行排序,这种方法完全没有考虑到数组是有序的前提条件,代码如下: 复制代码 代码如下: function concatSort(arrA,arrB){      return arrA.concat(arrB).sort(); } 为了弄清楚sort排序到

  • JS中数组实现代码(倒序遍历数组,数组连接字符串)

    Js中的数组是一种特殊的对象,用来表示偏移量的索引是该对象的属性. 具体代码如下所示: // =================== 求最大值===================================== <script> var arr = [10,35,765,21345,678,89]; var max = arr [0]; for (var i=0;i< arr.length;i++) { if (max<arr[i]){ max = arr [i]; } }

  • Angular.js中数组操作的方法教程

    前言 前端技术的发展是如此之快,各种优秀技术.优秀框架的出现简直让人目不暇接,紧跟时代潮流,学习掌握新知识自然是不敢怠慢.最近在学习Angular.js,将自己学习的一些经验技巧分享给大家,下面本文将给大家介绍关于Angular.js中数组操作的相关资料,话不多说了,来一起看看详细的介绍. 1:ng-click,ng-model,ng-bind,ng-class,ng-hide,ng-app 2:placeholder, 3:{}中加入代码":true|false",使用逗号隔开,可以

  • 详谈js中数组(array)和对象(object)的区别

    •object 类型: ◦ 创建方式: /*new 操作符后面Object构造函数*/ var person = new Object(); person.name = "lpove"; person.age = 21; /*或者用对象字面量的方法*/ var person = { name: "lpove"; age : 21; } •array类型 ◦ 创建方式: `var colors = new Array("red","blu

  • 探讨js字符串数组拼接的性能问题

    我们知道,在js中,字符串连接是性能最低的操作之一. 例如: 复制代码 代码如下: var text="Hello";  text+=" World!"; 早期浏览器没有对这种运算进行优化. 由于字符串是不可变的,这意味着要创建中间字符串来存储连接的结果.频繁地在后台创建和销毁字符串导制性能异常低下. 因此,可以利用数组对象进行优化. 例如: var buffer=[],i=0; buffer[i++]="Hello"; //通过相应索引值添加元

  • js array数组对象操作方法汇总

    js 数组对象操作方法如下: 1. 创建数组 var array1 = [1,2] //方法一 var array2 = new Array() //方法二 array[0] = 1; array[1] = 2; 2.遍历数组 for循环 和for...in 循环 var array1 = [1,2]; var l = array1.length; //for循环 for(var i=0;i< l;i++){ console.log(array1 [i]); } //for...in 循环 fo

  • JavaScript删除有序数组中的重复项

    JavaScript删除有序数组中的重复项

    目录 如果有一个有序数组 nums ,要求原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度. 不要使用额外的数组空间,必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成. 说明: 为什么返回数值是整数,但输出的答案是数组呢? 注意:输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的. 你可以想象内部操作如下: // nums 是以"引用"方式传递的.也就是说,不对实参做任何拷贝 int len = removeDu

  • 28个JS常用数组方法总结

    目录 1.Array.map() 2.Array.filter() 3.Array.reduce() 4.Array.reduceRight() 5.Array.fill() 6.Array.find() 7.Array.indexOf() 8.lastIndexOf() 9.Array.findIndex() 10.Array.includes() 11.Array.pop() 12.Array.push() 13.Array.shift() 14.Array.unshift() 15.Arr

  • js从数组中删除指定值(不是指定位置)的元素实现代码

    引用自百度知道里面的一个问答 例如数组{1,2,3,4,5} 要把数组里面的3删除得到{1,2,4,5} js代码: <script type="text/javascript"> Array.p Array.prototype.indexOf = function(val) { //prototype 给数组添加属性 for (var i = 0; i < this.length; i++) { //this是指向数组,this.length指的数组类元素的数量 i

随机推荐