Учитывая 2 отсортированных массива целых чисел, найдите n-е наибольшее число в сублинейном времени

Ответ 1

Я думаю, что это два параллельных бинарных поиска на подмассивах A[0..n-1] и B[0..n-1], которые являются O (log n).

• Учитывая отсортированные массивы, вы знаете, что n-е наибольшее будет отображаться где-то раньше или в A[n-1], если оно находится в массиве A или B[n-1], если оно находится в массиве B
• Рассмотрим элемент в индексе A в A и элемент в индексе B в B.
• Выполните двоичный поиск следующим образом (довольно грубый псевдокод, не принимая во внимание одноразовые проблемы):
  • Если a + b > n, уменьшите набор поиска
    • if A[a] > B[b], затем b = b / 2, else a = a / 2
  • Если a + b < n, увеличьте набор поиска
    • if A[a] > B[b], затем b = 3/2 * b, else a = 3/2 * a (на полпути между A и предыдущим A)
  • Если a + b = n, то n-е наибольшее будет max(A[a], B[b])

Я считаю наихудший случай O (ln n), но в любом случае определенно сублинейным.

Ответ 2

Я считаю, что вы можете решить эту проблему, используя вариант бинарного поиска. Интуиция, стоящая за этим алгоритмом, выглядит следующим образом. Пусть два массива A и B и пусть для простоты предполагают, что они одного размера (это не обязательно, как вы увидите). Для каждого массива мы можем построить параллельные массивы Ac и Bc такие, что для каждого индекса я Ac [i] - количество элементов в двух массивах, которые не больше A [i] и Bc [i] - это число элементов в двух массивах, не больших B [i]. Если бы мы могли эффективно строить эти массивы, то мы могли бы найти k-й наименьший элемент эффективно, выполнив двоичные поиски на Ac и Bc, чтобы найти значение k. Соответствующая запись A или B для этой записи является k-м наибольшим элементом. Бинарный поиск действителен, потому что два массива Ac и Bc сортируются, что, я думаю, вы можете легко убедить себя.

Конечно, это решение не работает в сублинейном времени, так как для построения массивов Ac и Bc требуется время O (n). Тогда возникает вопрос: существует ли способ, которым мы можем неявно строить эти массивы? То есть, можем ли мы определить значения в этих массивах, не обязательно строя каждый элемент? Я думаю, что ответ "да", используя этот алгоритм. Пусть начнется поиск массива A, чтобы увидеть, имеет ли оно k-е наименьшее значение. Мы знаем, что k-е наименьшее значение не может появляться в массиве в массиве A после положения k (при условии, что все элементы различны). Поэтому давайте сосредоточимся только на первых k элементах массива A. Мы проведем двоичный поиск по этим значениям следующим образом. Начало в позиции k/2; это k/2-й наименьший элемент в массиве A. Теперь выполните двоичный поиск в массиве B, чтобы найти наибольшее значение в B, меньшее этого значения, и посмотрите на его позицию в массиве; это число элементов в B, меньшее, чем текущее значение. Если мы складываем положение элементов в и B, мы имеем общее количество элементов в двух массивах, меньших текущего элемента. Если это точно k, мы закончили. Если это меньше k, то мы возвращаем в верхнюю половину первых k элементов A, а если это больше k, мы рекурсируем в нижней половине первых элементов k и т.д. В конце концов, мы либо что k-й наибольший элемент находится в массиве A, и в этом случае мы закончили. В противном случае повторите этот процесс в массиве B.

Время выполнения для этого алгоритма выглядит следующим образом. Поиск массива A выполняет двоичный поиск по k элементам, который принимает итерации O (lg k). Каждая итерация стоит O (lg n), так как мы должны выполнить двоичный поиск в B. Это означает, что общее время для этого поиска равно O (lg k lg n). Время, необходимое для этого в массиве B, одинаково, поэтому чистая среда выполнения для алгоритма O (lg k lg n) = O (lg ² n) = o (n), которая является сублинейной.

Ответ 3

Это довольно похожий ответ на вопрос Кирка.

Пусть Find( nth, A, B ) - функция, которая возвращает n-е число, и | A | + | B | >= n. Это простой псевдокод, не проверяя, является ли один из массива небольшим, менее трех элементов. В случае малого массива достаточно одного или двух бинарных поисков в более крупном массиве, чтобы найти нужный элемент.

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).

Ответ 4

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);

Ответ 5

Сублинейно, что? У вас не может быть алгоритма, который не проверяет хотя бы n элементов, даже если проверка решения потребует проверки многих. Но размер проблемы здесь должен обязательно означать размер массивов, поэтому алгоритм, который проверяет только n элементов, является сублинейным.

Итак, я думаю, что здесь нет трюка, начните с списка с меньшим стартовым элементом и продвигайтесь до тех пор, пока вы не выполните:

• Достигните n-й элемент, и все готово.
• Найти следующий элемент больше, чем следующий элемент в другом списке, после чего вы переключаетесь на другой список.
• Выключить элементы и переключиться.