合并两个有序数组为一个有序数组

/* 合并两个有序数组为一个有序数组
 * var a = [1, 2, 3, 4]
 * var b = [2, 5, 7, 9]
 */

/* 不去重 
 * var c = [1, 2, 2, 3, 4, 5, 7, 9]
 */
var loop = function (a, b) {
    var c = []
    var j = 0
    var i = 0
    var aLen = a.length
    var bLen = b.length
    if (a[j] < b[i]) {
        c.push(a[j])
        j++
        if (j < aLen) {
            loop()
        } else {
            c = c.concat(b.slice(i, bLen))
        }
    } else {
        c.push(b[i])
        i++
        if (i < bLen) {
            loop()
        } else {
            c = c.concat(a.slice(j, aLen))
        }
    }
    return c;
}
loop(a, b);

/* 去重 
 * var c = [1, 2, 3, 4, 5, 7, 9]
 * 利用两个数组有序这个条件，只需两个指针分别指向两个数组，当其中一个小于另外一个就移动该指针，反之则移动另外一个指针，如果相等则均向后移动
 * 结束条件：当任意一个数组的指针移到末尾则跳出循环
 * 那么只需把另外一个数组没有比较完的部分直接用concat拼到新数组后面
 */
let sortArr = (arr1, arr2) => {
    let i = 0, j = 0;
    let newArr = [];
    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] < arr2[j]) {
            newArr.includes(arr1[i]) ? '' : newArr.push(arr1[i]);
            i++
        } else if (arr1[i] > arr2[j]) {
            newArr.includes(arr2[j]) ? '' : newArr.push(arr2[j]);
            j++;
        } else if (arr1[i] === arr2[j]) {
            newArr.includes(arr1[i]) ? '' : newArr.push(arr1[i]);
            i++ , j++;
        }
    }

    // 将指针未移到末尾的部分取出,拼到新数组后面
    if (i < arr1.length) {
        return newArr.concat(arr1.splice(i))
    } else if (j < arr2.length) {
        return newArr.concat(arr2.splice(j))
    } else {
        return newArr
    }
}

扩展：多个有序数组合并为一个有序数组的算法

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

数组合并为一个有序数组? 方法一：

// 数组整体合并，然后sort排序
let ret=arr.reduce((arr1,arr2)=>arr1.concat(arr2)).sort((a,b)=>a-b);
ret=Array.from(new Set(ret));
console.log(ret);

但是上面的代码没有充分利用数组子元素本身就是有序数组这一特性

方法二：

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) {

    //记录每一个数组循环比较时的下标变化
    function filterIndexArr() {
        indexArr = indexArr.filter((item, index) => {
            return item.count < arr[item.index].length;
        });
    }

    //将每次比较的元素放进一个临时数组里面，取出最小值放入ret
    function pushToArr(arr) {
        let minVal = arr[0].val;
        let increaseArr = [arr[0].index];
        arr.forEach((item, index) => {
            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) {
        //循环比较每个数组的第一个元素
        compareArr = indexArr.map((item, index) => {
            return {
                index: item.index,
                val: arr[item.index][item.count]
            }
        });
        pushToArr(compareArr);
    }
    //取出最后不需要比较的数组元素，直接拼接到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);

sunnychuai / blog

合并两个有序数组为一个有序数组 #4