Возможный дубликат:
Как найти k-й наименьший элемент в объединении двух отсортированных массивов?
Это вопрос, который один из моих друзей сказал мне, что его попросили во время собеседования, я думал о решении.
Сублинейное время подразумевает логарифмический для меня, поэтому, возможно, какой-то метод разделения и завоевания. Для простоты предположим, что оба массива одного размера и что все элементы уникальны.
Я думаю, что это два параллельных бинарных поиска на подмассивах A[0..n-1] и B[0..n-1], которые являются O (log n).
A[n-1], если оно находится в массиве A или B[n-1], если оно находится в массиве BA в A и элемент в индексе B в B.a + b > n, уменьшите набор поиска
A[a] > B[b], затем b = b / 2, else a = a / 2a + b < n, увеличьте набор поиска
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), но в любом случае определенно сублинейным.
Я считаю, что вы можете решить эту проблему, используя вариант бинарного поиска. Интуиция, стоящая за этим алгоритмом, выглядит следующим образом. Пусть два массива 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 2 n) = o (n), которая является сублинейной.
Это довольно похожий ответ на вопрос Кирка.
Пусть 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).
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);
Сублинейно, что? У вас не может быть алгоритма, который не проверяет хотя бы n элементов, даже если проверка решения потребует проверки многих. Но размер проблемы здесь должен обязательно означать размер массивов, поэтому алгоритм, который проверяет только n элементов, является сублинейным.
Итак, я думаю, что здесь нет трюка, начните с списка с меньшим стартовым элементом и продвигайтесь до тех пор, пока вы не выполните: