两个排序的整数数组 A[1..N]
和 B[1..N]
按升序提供。
问题:设计一个O(log N)-time
算法来找出所有 2N 个整数的中位数。 N 可能不是 2 的幂。
为了简单起见,我们可以假设 O(1)
算法返回 m
这样:
2^m < N < 2^m+1
我的问题:
N
可能不是2
的幂,这是什么意思? (明白了)- 我不知道如何更改输入并使长度成为 2 的幂 在找到
min
和max
之后来自数组A
和B
的元素。
最佳答案
您可以使用二进制搜索方式在 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 2 3 => 2
1 2 3 => 2
现在我们已经有了一个一致的中值,但基本思想是继续丢弃两个数组中每一个中的一半条目,直到我们有一个中值。
此算法的性能与二分查找一样好,即 O(logN)
。
关于algorithm - Clog n的一个算法问题的设计[C++代码],我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45691363/