Clog n算法问题的设计[C ++代码] [英] Design of an algorithm problems of Clog n[C++ code]

问题描述

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

Two sorted arrays of integers A[1..N] and B[1..N] are provided in ascending order.

Q:Design 一种O(log N)-time算法，用于找出所有2N个整数的中位数. N的幂不能为2 .

Q:Design an O(log N)-time algorithm for finding out the median of all 2N integers. N may not power of 2.

为了简单起见，我们可以假设O(1)算法返回m，这样:

To make thing easy, we can assume O(1) algorithm which return m such that:

2^m < N <  2^m+1

我的问题:

1. N可能不是2的幂，这是什么意思? (了解)
2. 在从数组A和min和max元素后，我不知道如何更改输入并使长度变为2的幂>.

1. N may not be power of 2, what does that mean? (understood)
2. I don't know how to change the input and make the length to power of 2 after found min and max elements from both array A and B.

推荐答案

您可以使用二进制搜索样式方法在O(logN)时间内解决此问题.考虑以下两个数组:

You can solve this in O(logN) time using a binary search style approach. Consider the following two arrays:

1 1 2 2 3
1 2 3 4 5

现在，合并的中位数为:

Now the combined median is:

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

让我们看看如何找到它.首先猜测中值是每个数组的中心:

Let's see how we can find it. Start by guessing that the median is the center of each array:

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

从逻辑上讲，我们知道组合的中位数不可能小于小于2或更大小于3.相反，它必须位于之间的某个地方这两个值.因此我们可以丢弃第一个数组小于小于2的所有内容，而第二个数组更大大于3的所有内容.这不会影响中位数的位置，因为我们正在丢弃组合中位数所在的两侧两侧的相等个元素.从概念上讲，这使我们拥有:

Logically, we know the combined median can't possibly be less than 2 or greater than 3. Rather, it must be somewhere in between these two values. So we can discard everything in the first array smaller than 2 and everything in the second array larger than 3. This won't affect the position of the median because we are discarding an equal number of elements on both sides of where the combined median is. Conceptually, this leaves us with:

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

现在我们已经有了一个一致的中值，但是基本思想是继续丢弃两个数组中每个数组的一半条目，直到我们有一个中值为止.

Now we already have an agreeing median, but the basic idea is to keep discarding half of the entries in each of the two arrays until we have a single median value.

此算法的执行效果与二进制搜索O(logN)一样.

This algorithm will perform as well as binary search, which is O(logN).

这篇关于Clog n算法问题的设计[C ++代码]的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！