给定两个排序的整数数组，在次线性时间内找到第n个最大数。

Question

可能重复：

How to find the kth smallest element in the union of two sorted arrays?

这是一个问题，我的一个朋友告诉我，他是在面试时被问到的，我一直在考虑一个解决办法。

次线性时间对我来说意味着对数，所以也许是某种分治的方法。为了简单起见，假设两个数组大小相同，所有元素都是唯一的

Answer 1

我认为这是对子数组A[0..n-1]和B[0..n-1]的两个并发二进制搜索，即O(log )。

给定排序数组的B

• Consider B.

• Perform

• ，您知道，如果是数组A，则在A[n-1]之前或在A[n-1]处出现第n个最大值，如果是在数组A中，则出现在B[n-1]中，如果是在A中的索引a处，则在索引b中出现以下项(不考虑“一次性”问题)：<代码>H 117如果a + b > n，则减少搜索集F 119H 120如果A[a] > B[b]则b = b / 2，否则a = a / 2

​

- If `a + b < n`, then increase the search set 
    - if `A[a] > B[b]` then `b = 3/2 * b`, else `a = 3/2 * a` (halfway between `a` and previous `a`)

​

- If `a + b = n` then the _nth_ largest is `max(A[a], B[b])`

​

我相信最坏的情况O( n)，但在任何情况下都肯定是次线性的。

Answer 2

这与柯克的回答非常相似。

设Find( nth, A, B )是返回n个数的函数，并设为回传n个数的函数。这是一个简单的伪码，不检查数组中的一个元素是否小，是否小于3个元素。在小数组的情况下，在较大数组中进行一个或两个二进制搜索就足以找到所需的元素。

Find( nth, A, B )
  If A.last() <= B.first():
    return B[nth - A.size()]
  If B.last() <= A.first():
    return A[nth - B.size()]
  Let a and b indexes of middle elements of A and B
  Assume that A[a] <= B[b] (if not swap arrays)
  if nth <= a + b:
    return Find( nth, A, B.first_half(b) )
  return Find( nth - a, A.second_half(a), B )

它是log(|A|) + log(|B|)，而且由于可以使输入数组具有n个元素，所以它具有log(n)复杂性。

Answer 3

int[] a = new int[] { 11, 9, 7, 5, 3 };
int[] b = new int[] { 12, 10, 8, 6, 4 };
int n = 7;
int result = 0;
if (n > (a.Length + b.Length))
    throw new Exception("n is greater than a.Length + b.Length");
else if (n < (a.Length + b.Length) / 2)
{
    int ai = 0;
    int bi = 0;
    for (int i = n; i > 0; i--)
    {
        // find the highest from a or b
        if (ai < a.Length)
        {
            if (bi < b.Length)
            {
                if (a[ai] > b[bi])
                {
                    result = a[ai];
                    ai++;
                }
                else
                {
                    result = b[bi];
                    bi++;
                }
            }
            else
            {
                result = a[ai];
                ai++;
            }
        }
        else
        {
            if (bi < b.Length)
            {
                result = b[bi];
                bi++;
            }
            else
            {
                // error, n is greater than a.Length + b.Length
            }
        }
    }
}
else
{
    // go in reverse
    int ai = a.Length - 1;
    int bi = b.Length - 1;
    for (int i = a.Length + b.Length - n; i >= 0; i--)
    {
        // find the lowset from a or b
        if (ai >= 0)
        {
            if (bi >= 0)
            {
                if (a[ai] < b[bi])
                {
                    result = a[ai];
                    ai--;
                }
                else
                {
                    result = b[bi];
                    bi--;
                }
            }
            else
            {
                result = a[ai];
                ai--;
            }
        }
        else
        {
            if (bi >= 0)
            {
                result = b[bi];
                bi--;
            }
            else
            {
                // error, n is greater than a.Length + b.Length
            }
        }
    }
}
Console.WriteLine("{0} th highest = {1}", n, result);