大概一年以前，接到同学面试头条之后讨论的请求，说是要在八分钟内手写出二路归并源码，我也没含糊，大概在八分钟内交出了源码，并且在 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) 上。不过我们依然有了优化的切入点（寻找最值）。
关于胜者树，败者树

内容目录

  1. 二路归并
  2. 思考
donation