问题为:两个已排序向量,如何以 $O(log(min(m, n)))$ 时间求出两个向量归并后的中位数?
用LeetCode4. 寻找两个正序数组的中位数的官方题解解法二,可以将问题扩展,以 $O(log(min(m, n)))$ 时间对两个向量归并后的向量进行k选取 。
代码见coding-practice仓 two_arrs_k_select_implementation2()
这个解法比教材P345代码12.9更简单,时间复杂度一样。
习题解析[12-10]:教材上的代码也可以扩展成对 $s_1 \bigcup s_2$ 进行k选取。