javascript實現(xiàn)將多個有序數(shù)組合并為一個有序數(shù)組的算法

hiYoHoo 發(fā)布于2019-08-20 18:13 / 996人閱讀

摘要：假設(shè)有這樣一個需求，一個數(shù)組的子元素全是有序數(shù)組，類似我們希望將上述數(shù)組合并為一個有序數(shù)組，怎么處理呢最簡單的方案就是將數(shù)組整體合并，然后排序，代碼如下但是上面的代碼沒有充分利用數(shù)組子元素本身就是有序數(shù)組這一特性，我們利用歸并排序算

假設(shè)有這樣一個需求，一個數(shù)組的子元素全是有序數(shù)組，類似：

let arr= [[1, 2], [0, 3, 4,4,4,6,7,8,9,10], [-1, 4],[-1,3],[-1],[100,200],[5,1000,30000]];

我們希望將上述數(shù)組合并為一個有序數(shù)組，怎么處理呢？

最簡單的方案就是：
將數(shù)組整體合并，然后sort排序，代碼如下：

let ret=arr.reduce((arr1,arr2)=>arr1.concat(arr2)).sort((a,b)=>a-b);
ret=Array.from(new Set(ret));
console.log(ret);

但是上面的代碼沒有充分利用數(shù)組子元素本身就是有序數(shù)組這一特性，我們利用“歸并排序”算法，可以大大的提高類似數(shù)組的合并排序性能，代碼(代碼里面有詳細注釋)如下：

let arr= [[1, 2], [0, 3, 4,4,4,6,7,8,9,10], [-1, 4],[-1,3],[-1],[100,200],[5,1000,30000]];
// let arr= [[1,2,3]];

function merge(arr){

    //記錄每一個數(shù)組循環(huán)比較時的下標(biāo)變化
    function filterIndexArr() {
        indexArr=indexArr.filter((item,index)=>{
            return item.count{
            if (minVal>item.val){
                minVal=item.val;
                increaseArr=[item.index];
            }else if (minVal==item.val && index!=0){
                increaseArr.push(item.index)
            }
        });
        increaseArr.forEach((item)=>{
            let thatItem=item;
            indexArr.forEach((item)=>{
                if (item.index==thatItem){
                    item.count++;
                }
            });
        });
        filterIndexArr();
        ret.push(minVal);
    }

    let ret=[];
    let indexArr=arr.map((item,index)=>{
        return {
            index,
            count:0
        }
    });
    filterIndexArr();

    let compareArr=[];
    while (indexArr.length>1){
        //循環(huán)比較每個數(shù)組的第一個元素
        compareArr=indexArr.map((item,index)=>{
            return {
                index:item.index,
                val:arr[item.index][item.count]
            }
        });
        pushToArr(compareArr);
    }
    //取出最后不需要比較的數(shù)組元素，直接拼接到ret后面
    let remainArr=arr[indexArr[0].index].slice(indexArr[0].count);
    ret=ret.concat(remainArr);
    ret=Array.from(new Set(ret));
    return ret;
}

let ret=merge(arr);
console.log(ret);

由于子數(shù)組本身有序，分別記錄要被比較數(shù)組的下標(biāo)，循環(huán)取出最小值push到ret就可以了，是不是很簡單。