Даны два отсортированных массива nums1 и nums2 длиной n и m соответственно, необходимо найти их медиану.
Если n + m нечетное, то медианой будет элемент по середине, иначе это среднее двух элементов.
Пример:
nums1 = [1,3], nums2 = [2]
Ответ: 2.00000
nums1 = [1,2], nums2 = [3,4]
Ответ: 2.50000
Существуют решения за O((n + m)*log(n + m)), O(n + m) и O(log(n + m))
По-хорошему, нужно найти O(log(n + m))
Решение:
O((n + m) * log(n + m)) - очевидно
O(n + m) - сливаем два массива за линию (они же отсортированные) и находим медиану
Найдем за O(log(n + m))
Идея следующая: чтобы найти медиану двух массивов, нужно найти такие два элемента в двух массивах, чтобы все элементы слева от этих двух элементов были меньше каждого элемента справа. Это делается бинарным поиском.
Предположим, что первый массив меньше. Если первый массив больше, то поменяйте массивы местами, чтобы убедиться, что первый массив меньше.
В этом алгоритме мы в основном используем два набора, выполняя двоичный поиск в меньшем массиве. Пусть mid1 - это разбиение меньшего массива. Первый набор содержит элементы от 0 до (mid1 – 1) из меньшего массива и элементы mid2 = ((n + m + 1) / 2 – mid1) из большего массива, чтобы убедиться, что в первом наборе ровно (n+m+1)/2 элемента. Второй набор содержит оставшиеся половинки элементов.
Наша цель - найти точку в обоих массивах таким образом, чтобы все элементы в первом наборе были меньше, чем все элементы в элементах другого набора (набора, который содержит элементы с правой стороны).
double medianOf2(vector<int> &a, vector<int> &b) {
int n = a.size(), m = b.size();
if (n > m)
return medianOf2(b, a);
int lo = 0, hi = n;
while (lo <= hi) {
int mid1 = (lo + hi) / 2;
int mid2 = (n + m + 1) / 2 - mid1;
int l1 = (mid1 == 0 ? INT_MIN : a[mid1 - 1]);
int r1 = (mid1 == n ? INT_MAX : a[mid1]);
int l2 = (mid2 == 0 ? INT_MIN : b[mid2 - 1]);
int r2 = (mid2 == m ? INT_MAX : b[mid2]);
if (l1 <= r2 && l2 <= r1) {
if ((n + m) % 2 == 0)
return (max(l1, l2) + min(r1, r2)) / 2.0;
else
return max(l1, l2);
}
if (l1 > r2)
hi = mid1 - 1;
else
lo = mid1 + 1;
}
return 0;
}
@algoses