Clog n[C++代码的算法问题设计].

Question

按升序提供了两个整数A[1..N]和B[1..N]的排序数组。

Q：设计一个O(log N)-time算法来找出所有 2N 个整数的中位数。N 不能 2 的幂。

为了简单起见，我们可以假设O(1)算法返回m，例如：

2^m < N <  2^m+1

我的问题：

1. N可能不是2的力量，这是什么意思？(理解(
2. 我不知道如何更改输入并使长度在从数组A和B中找到min和max元素后变为2 的幂。

Answer 1

您可以使用二叉搜索样式的方法O(logN)解决此问题。 请考虑以下两个数组：

1 1 2 2 3
1 2 3 4 5

现在的组合中位数是：

1 1 1 2 2 2 3 3 4 5 => 2

让我们看看如何找到它。 首先猜测中位数是每个数组的中心：

1 1 2 2 3 => 2
1 2 3 4 5 => 3

从逻辑上讲，我们知道组合中位数不可能小于2 或大于3。 相反，它必须介于这两个值之间。 因此，我们可以丢弃第一个数组中小于 2 的所有内容和第二个数组中大于 3 的所有内容。 这不会影响中位数的位置，因为我们丢弃了组合中位数所在两侧相同数量的元素。从概念上讲，这给我们留下了：

2 2 3 => 2
1 2 3 => 2

现在我们已经有一个同意的中位数，但基本的想法是继续丢弃两个数组中每个数组中的一半条目，直到我们有一个中值。

该算法将执行与二叉搜索一样，这是O(logN)。