javascript怎么将一个由多个有序数组组成的数组合并为一个有序数组？

Question

问题也可以描述为：将多个有序数组合并为一个有序数组？比如将[[1,2],[0,3,5],[-1,4]]合并出一个[-1, 0, 1, 2, 3, 4, 5],如果不考虑去重怎么写？考虑去重又怎么写？

Answer 1

不考虑去重

var arr = [[1, 2], [0, 3, 5], [-1, 4]];
arr = arr
    .reduce((a, b) => a.concat(b), [])
    .sort((a, b) => a - b); // 如果需要从小到大排序加上这个

console.log(arr);

结果：

考虑去重

思路是使用对象的键名来缓存数字，然后用Object.keys取所有键名（利用了对象键名唯一性）

var arr = [[1, 2], [0, 3, 5], [-1, 4]];
var obj = {};

arr = arr
    .forEach(item => item.forEach(function(num) {
        obj[num] = true;
    }));
arr = Object
    .keys(obj)
    .map(num => +num) // 这行主要是将键名取出来之后，数组中全部是字符串，将其都转成数字，以便后面排序
    .sort((a, b) => a - b);

console.log(arr);

结果：

Answer 2

将就看吧，如果要改变排序方式就改 sort

Answer 3

javascript的concat()方法

举个栗子：

<script type="text/javascript">

var arr = new Array(3)
arr[0] = "George"
arr[1] = "John"
arr[2] = "Thomas"

var arr2 = new Array(3)
arr2[0] = "James"
arr2[1] = "Adrew"
arr2[2] = "Martin"

document.write(arr.concat(arr2))

</script>

结果输出：

George,John,Thomas,James,Adrew,Martin

已经得到一个集合了，一个集合的去重不是什么有难度的算法，给你自己实现吧。

Answer 4

有序数组的合并完全可以做到 O(n) 不需要排序。

供参考

var arrs = [[1, 2], [0, 3, 4, 5], [-1, 4]]

/**
 * @param {Array[]} arrs
 * @param {boolean=false} [isUnique]
 * @param {Function=(a, b) => a - b} [compare]
 * @returns {Array}
 */
function join (arrs, isUnique = false, compare = (a, b) => a - b) {
  if (!Array.isArray(arrs)) { return [] }

  var result = []

  arrs.forEach(arr1 => {
    arr1 = Array.isArray(arr1) ? arr1.slice() : [arr1]
    let arr2 = result
    result = []

    while (arr1.length > 0 && arr2.length > 0) {
      result.push(compare(arr1[0], arr2[0]) <= 0 ? arr1.shift() : arr2.shift())
    }

    result = result.concat(arr1, arr2)

    if (isUnique) {
      result = Array.from(new Set(result))
    }
  })

  return result
}

console.log(join(arrs)) // [ -1, 0, 1, 2, 3, 4, 4, 5 ]
console.log(join(arrs, true)) // [ -1, 0, 1, 2, 3, 4, 5 ]

Answer 5

谢邀！
用最简单的方法吧
1.先把每一个数组合并起来先

var arr=[[1,2],[0,3,5],[-1,4]]
arr=arr.reduce(function (n1,n2) {return n1.concat(n2)});

2.然后排序

arr=arr.sort(function(n1,n2){return n1-n2});

3.如果需要去重

arr=arr.filter(function(item,index,self){
return self.indexOf(item) == index;

});
如果想合成一句代码

arr=arr.reduce(function (n1,n2) {return n1.concat(n2)}).sort(function(n1,n2){return n1-n2}).filter(function(item,index,self){return self.indexOf(item) == index;})

用es6就依葫芦画瓢

arr=arr.reduce((n1,n2) => n1.concat(n2)).sort((n1,n2) => n1-n2).filter((item,index,self)=>self.indexOf(item) == index;)

不过es6的话，去重最好是用Array.from和Set。举个栗子。在我之前写的文章有说到这些！编写自己的代码库（javascript常用实例的实现与封装）

//ES6新增的Set数据结构，类似于数组，但是里面的元素都是唯一的 ，其构造函数可以接受一个数组作为参数
//let arr=[1,2,1,2,6,3,5,69,66,7,2,1,4,3,6,8,9663,8]
//let set = new Set(array);
//{1,2,6,3,5,69,66,7,4,8,9663}
//ES6中Array新增了一个静态方法from，可以把类似数组的对象转换为数组
//Array.from(set)
//[1,2,6,3,5,69,66,7,4,8,9663]
function removeRepeatArray(arr){
    return Array.from(new Set(arr))
}

Answer 6

就是归并排序的变体

function merge(array){
    if(array.length<1){
        return;
    }else if(array.length===1){
        return array[0];
    }else{
        var ret=[];
        var child=array.splice(0,1)[0];
        array=merge(array);
        var ci=0;
        var ai=0;
        while(ci<child.length&&ai<array.length){
            if(child[ci]<array[ai]){
                ret.push(child[ci]);
                ci++;
            }else if(child[ci]===array[ai]){
                ret.push(child[ci]);
                ci++;
                ai++;
            }else{
                ret.push(array[ai]);
                ai++
            }
        }
        while(ci<child.length){
            ret.push(child[ci]);
            ci++;
        }
        
        while(ai<array.length){
            ret.push(ret[ai]);
            ai++;
        }
        
        return ret;
    }
}

var arr=[[0,1,3,5,8],[-1,0,4,6,7]];
var ret=merge(arr);
console.log(ret);

Answer 7

谢邀。

不考虑去重：

function flat(arr) {
    const list = [];
    arr.forEach(a => Array.prototype.push.apply(list, a));
    return list;
}

flat([[1, 2], [0, 3, 5], [-1, 4]]).sort();  // [-1, 0, 1, 2, 3, 4, 5]

考虑去重：

function flatDistinct(arr) {
    const o = {};
    arr.forEach(a => a.forEach(i => o[i] = null));
    return Object.keys(o).map(i => Number(i));
}

flatDistinct([[1, 2], [0, 3, 5], [-1, 4]]).sort();  // [-1, 0, 1, 2, 3, 4, 5]