Вопрос:
Предположим, что у нас есть 2 отсортированных массива целых чисел с размерами n и m. Каков наилучший способ найти медиану всех чисел m + n?
Это легко сделать с помощью сложности log(n) * log(m). Но я хочу решить эту проблему в log(n) + log(m) времени. Так есть ли предложение решить эту проблему?
Лучший ответ:
Объяснение
Ключевой момент этой проблемы состоит в том, чтобы игнорировать половину A и B каждого шага рекурсивно, сравнивая медиану оставшихся A и B:
if (aMid < bMid) Keep [aMid +1 … n] and [bLeft … m] else Keep [bMid + 1 … m] and [aLeft … n] // where n and m are the length of array A and B
В качестве следующего: временная сложность O(log(m + n))
public double findMedianSortedArrays(int[] A, int[] B) { int m = A.length, n = B.length; int l = (m + n + 1) / 2; int r = (m + n + 2) / 2; return (getkth(A, 0, B, 0, l) + getkth(A, 0, B, 0, r)) / 2.0; } public double getkth(int[] A, int aStart, int[] B, int bStart, int k) { if (aStart > A.length — 1) return B[bStart + k — 1]; if (bStart > B.length — 1) return A[aStart + k — 1]; if (k == 1) return Math.min(A[aStart], B[bStart]); int aMid = Integer.MAX_VALUE, bMid = Integer.MAX_VALUE; if (aStart + k/2 — 1 < A.length) aMid = A[aStart + k/2 — 1]; if (bStart + k/2 — 1 < B.length) bMid = B[bStart + k/2 — 1]; if (aMid < bMid) return getkth(A, aStart + k / 2, B, bStart, k — k / 2); // Check: aRight + bLeft else return getkth(A, aStart, B, bStart + k / 2, k — k / 2); // Check: bRight + aLeft }
Надеюсь, это поможет! Дайте мне знать, если вам нужно больше объяснений в любой части.
Ответ №1
Здесь очень хорошее решение, которое я нашел в Java на Stack Overflow. Это метод поиска наименьших элементов K и K + 1 в двух массивах, где K центр объединенного массива.
Если у вас есть функция для нахождения элемента Kth из двух массивов, то найти медиану этих двух легко:
- Рассчитать средневзвешенное значение Kth и Kth + 1 элементов X и Y
Но тогда вам понадобится способ найти элемент Kth из двух списков; (помните, что мы сейчас индексируем)
-
Если X содержит нулевые элементы, то K-й наименьший элемент X и Y является K-м наименьшим элементом из Y
-
В противном случае, если K == 2, то второй наименьший элемент X и Y является наименьшим из наименьших элементов X и Y (min (X [0], Y [0]))
-
В противном случае;
я. Пусть A – min (длина (X), K/2)
II. Пусть B – min (длина (Y), K/2)
III. Если X [A] > Y [B], то повторите с шага 1. с X, Y ‘со всеми элементами из Y из B в конец Y и K’ = K – B, иначе рекурсия с X ‘со всеми элементами X от A до конца X, Y и K ‘= K – A
Если я найду время завтра, я проверю, что этот алгоритм работает на Python, как указано, и предоставляет пример исходного кода, он может иметь некоторые ошибки “один за другим” как есть.
Ответ №2
Возьмите медианный элемент в списке A и назовите его a. Сравните a с центральными элементами в списке B. Позволяет называть их b1 и b2 (если B имеет нечетную длину, то именно там, где вы разбиваете b, зависит ваше определение медианы от четного списка длины, но процедура почти идентична независимо). если b1 & leq; a & leq; b2, то a является медианой объединенного массива. Это можно сделать в постоянное время, поскольку для этого требуется ровно два сравнения.
Если a больше, чем b2, мы добавляем верхнюю половину A в верхнюю часть B и повторяем. B больше не будет сортироваться, но это не имеет значения. Если a меньше, чем b1, мы добавляем нижнюю половину A в нижнюю часть B и повторяем. Они будут перехватывать log (n) раз больше (если медиана найдена раньше, а затем, конечно, останавливается).
Возможно, что это не нашло медианы. Если это так, то медиана находится в B. Если это так, выполните тот же алгоритм, что и A и B. Для этого потребуются итерации log (m). Всего вы выполнили не более 2 * (log (n) + log (m)) итераций операции с постоянным временем, поэтому вы решили проблему в журнале log (n) + log (m).
Это, по сути, тот же ответ, который был задан iehrlich, но выписан более явно.
Ответ №3
Да, это можно сделать. Учитывая два массива, A и B, в худшем случае вы должны сначала выполнить двоичный поиск в A, а затем, если он не удается, двоичный поиск в B ищет медиану. На каждом шаге бинарного поиска вы проверяете, является ли текущий элемент фактическим медианом объединенного массива A+B. Такая проверка занимает постоянное время.
Посмотрим, почему такая проверка является постоянной. Для простоты предположим, что |A| + |B| является нечетным числом и что все числа в обоих массивах различны. Вы можете удалить эти ограничения позже, применив обычный медианный подход определения (например, как вычислить медиану массива, содержащего дубликаты, или массив с четной длиной). Во всяком случае, учитывая это, мы точно знаем, что в объединенном массиве будут (|A| + |B| — 1) / 2 элементы справа и слева от фактической медианы. В процессе двоичного поиска в A мы знаем индекс текущего элемента x в массиве A (пусть это будет i). Теперь, если x удовлетворяет условию B[j] < x < B[j+1], где i + j == (|A| + |B| — 1) / 2, то x является вашей медианной.
Общая сложность – это O(log(max(|A|, |B|)) время и O(1) память.
