Как можно ускорить код возврата медианы двух отсортированных массивов?
Задача с leetcode. Текст задачи:
Учитывая два отсортированных массива nums1 и nums2 размера m и n соответственно, вернуть медиану двух отсортированных массивов. Общая сложность времени выполнения должна быть O(log (m+n)).
Саму задачу я решил уже, но хочу добиться максимально быстрого решения. На данный момент достиг максимально возможного для себя 160 ms и 39.2 MB. Как можно код сделать оптимальнее по скорости и потребления памяти?
public class Solution
{
public double FindMedianSortedArrays(int[] nums1, int[] nums2)
{
nums1 = Concat(nums1, nums2);
SortArray(nums1, 0, nums1.Length - 1);
if (nums1.Length % 2 == 0)
{
double a = nums1[nums1.Length / 2 - 1];
double b = nums1[nums1.Length / 2];
double result = (a + b) / 2;
return result;
}
return Convert.ToDouble(nums1[nums1.Length / 2]);
}
private int[] Concat(int[] x, int[] y)
{
int oldLen = x.Length;
Array.Resize(ref x, x.Length + y.Length);
Array.Copy(y, 0, x, oldLen, y.Length);
return x;
}
private void SortArray(int[] array, int leftIndex, int rightIndex)
{
var i = leftIndex;
var j = rightIndex;
var pivot = array[leftIndex];
while (i <= j)
{
while (array[i] < pivot)
{
i++;
}
while (array[j] > pivot)
{
j--;
}
if (i <= j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}
if (leftIndex < j)
SortArray(array, leftIndex, j);
if (i < rightIndex)
SortArray(array, i, rightIndex);
}
}
Ответы (2 шт):
Для решения этой задачи нужен двойной двоичный (бинарный) поиск.
Обозначим исходные массивы A[1..n] и B[1..m]. Тогда нам надо найти такой число X, что количество элементов в A и B, которые ≤ X, равно (n+m)/2 (если это число не целое, то оба округления допустимы).
Попробуем поискать это число в первом массиве. Возьмём для начала X=A[i] и найдём сколько элементов в массиве B ≤ X, пусть это количество равно j = j(i). Так как массив B упорядочен, это число можно найти двоичным поиском. Но теперь количество элементов, которые ≤ X в обоих массивах, равно i + j.
Заметим, что получившаяся функция, f(i) = i + j(i), является монотонной. А значит, можно найти искомое (n+m)/2 среди её значений ещё одним двоичным поиском. И если оно нашлось - значит, A[i] и есть медиана.
Возможен также вариант, когда среди значений f(i) не нашлось (n+m)/2, а нашлось только что-то меньшее. Это значит, что искомая медиана лежит в массиве B. Обозначим максимальное i, для которого f(i) < (n+m)/2 (такое i должно было быть уже найдено неудачным двоичным поиском на прошлом шаге), тогда медиана должна быть B[(n+m)/2 - i]
Решение
NB Индексация массивов с нуля. И порядковые статистики тоже нумеруются с нулевой.
Правда ли что nums1[i] - k-тая порядковая статистика в объединении массивов nums1 и nums2?
Вычислим j = k - i. Если в объединённом массиве перед nums1[i] окажутся ровно j элементов из nums2, то ответ да. Для этого достаточно выполнения неравенства nums2[j - 1] <= nums1[i] <= nums2[j]. Если оно выполнено, то перед nums1[i] окажутся ровно j элементов из nums2 и i элементов из nums1. А сам он окажется на месте с номером j + i (= k).
Определим метод CheckOrderStatistic(nums1, nums2, i, k) который возвращает 0 если nums1[i] - k-тая порядковая статистика. Также он возвращает -1 если нарушается условие nums1[i] <= nums2[j] и 1 если нарушено условие nums2[j - 1] <= nums1[i].
Пример:
nums1 = [0, 1, 3, 4, 6, 7], nums2 = [2, 5], k = 3
i 0 1 2 3 4 5 CheckOrderStatistic(nums1, nums2, i, k) -1 -1 0 1 1 1
Значения возрастают, можно применить двоичный поиск по i. Ищем ноль. Его может не быть. Это значит что на месте k находится элемент из массива nums2. В этом случае меняем местами nums1 и nums2 и выполняем ещё один двоичный поиск.
Сложность алгоритма O(log(m) + log(n)), где m и n длины массивов. В терминах О-большого O(log(m) + log(n)) = O(log(m + n)). Что и требовалось в условиях задачи.
Сравнение
Это решение не покажется вам быстрее чем решение с сортировкой. Массивы длиной не более 1000 элементов. На таких размерах всё время уходит на загрузку программы в память. 160 ms и 39.2 MB - всё время и память потребляются рантаймом C#. Например память под массивы в задаче не превосходит восьми килобайт. Восемь килобайт на фоне 40 мегабайт. Со временем та же ситуация - на сортировку потребуются микросекунды на фоне миллисекунд. Не о чем говорить. Не даром в обсуждении решений на Литкоде всё сплошь сортировки и иногда слияния.
Чтобы измерить разницу между решениями нужны миллионы или миллиарды элементов. Тогда станет очевидно, что двоичный поиск быстрее. И это при условии что будет измеряться время исполнения одной функции решающей задачу, не всей программы.
Код
Код проходит все тесты на Литкоде. По памяти и скорости где по-середине. Почему - я объяснил выше.
public class Solution {
public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
int n = nums1.Length + nums2.Length;
int k1 = (n - 1) / 2;
int k2 = (n - 1) - k1;
double s1 = OrderStatistic(nums1, nums2, k1);
double s2 = OrderStatistic(nums1, nums2, k2);
return (s1 + s2) / 2;
}
// checks if nums1[i] is k-th order statistic in merged array
private int CheckOrderStatistic(int[] nums1, int[] nums2, int i, int k) {
int j = k - i;
if (j < 0) {
return 1;
}
if (nums2.Length < j) {
return -1;
}
// nums2[j - 1] <= nums1[i]
if (0 < j && nums2[j - 1] > nums1[i]) {
return -1;
}
// nums1[i] <= nums2[j]
if (j < nums2.Length && nums1[i] > nums2[j]) {
return 1;
}
return 0;
}
private int Search(int[] nums1, int[] nums2, int k) {
if (nums1.Length == 0) {
return -1;
}
int lo = 0;
int hi = nums1.Length - 1;
int r_lo = CheckOrderStatistic(nums1, nums2, lo, k);
if (r_lo == 0) {
return lo;
}
if (r_lo > 0) {
return -1;
}
int r_hi = CheckOrderStatistic(nums1, nums2, hi, k);
if (r_hi == 0) {
return hi;
}
if (r_hi < 0) {
return -1;
}
while(lo < hi - 1) {
int mid = (lo + hi) / 2;
int r_mid = CheckOrderStatistic(nums1, nums2, mid, k);
if (r_mid == 0) {
return mid;
}
if (r_mid < 0) {
lo = mid;
} else {
hi = mid;
}
}
return -1;
}
private int OrderStatistic(int[] nums1, int[] nums2, int k) {
int i1 = Search(nums1, nums2, k);
if (i1 != -1) {
return nums1[i1];
}
int i2 = Search(nums2, nums1, k);
return nums2[i2];
}
}