arrays - 从 A union B 中找到第 k 个最小元素

Question

在 2 个大小为 n 的排序数组 A 和 B 中，如何在 O(log n) 时间内找到 A union B 中的第 k 个最小元素？我知道找到 A union B 需要 O(n)。

Answer 1

这可以通过以下方式在 O(log n) 时间内完成：

主要要做的事情：由于数组已排序，您可以使用二进制搜索在 B 中查找 A 的元素。

整体解决方案：http: //leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html