多路归并

大概一年以前，接到同学面试头条之后讨论的请求，说是要在八分钟内手写出二路归并源码，我也没含糊，大概在八分钟内交出了源码，并且在 10 分钟内完成了边界调试，最终跑通了代码。只可惜最终同学因为没能现场写出这道决定性的题目被刷了下来。

二路归并

/*
 * time complexity = O(n)
 */
function twoWayMerge (arr1, arr2) {
    if (!arr1 || !arr2) {
        return 'illegal params'
    }
    
    if (arr1.length === 0 || arr2.length === 0) {
        return arr1.concat(arr2)
    }

    const result = []
    let i = 0, j = 0

    while (i < arr1.length && j < arr2.length) {
        if(arr1[i] <= arr2[j]) {
            result.push(arr1[i])
            i++
        } else {
            result.push(arr2[j])
            j++
        }
    }

    if (i > arr1.length - 1) {
        result.push(...arr2.slice(j))
    } else {
        result.push(...arr1.slice(i))
    }

    return result
}

/*
 * time complexity = O(n*(k-1))
 */
function multiWaysMerge (...args) {
    return args.reduce(twoWayMerge)
}

multiWaysMerge([0, 2, 4, 6, 8], [0, 2, 3, 5, 7], [0, 2, 4, 6, 8], [0, 2, 3, 5, 7], [0, 2, 4, 6, 8], [0, 2, 3, 5, 7])

思考

使用 reduce 函数很容易得将多路归并反复进行两两归并来实现。然而真的只能限制在平方级别的时间复杂度了嘛？换个思路，不以二路归并为核心子函数，尝试使用另外一种思路，把多路归并按照二路归并的方式来思考，二路归并是同步对比两路的同位置元素，小的放入结果数组，并指向下一个元素，反复之直到两个数组有一个遍历结束。我们可以把对比两路换成对比 k 路，接下来的思路和二路归并完全一致，不过由于不再是两个数的对比，在一个序列中寻找最值用循环的话需要 O(k)，这样时间复杂度还是落在了 O(nk) 上。不过我们依然有了优化的切入点（寻找最值）。
关于胜者树，败者树