Ссылка на код сложность (log (n) + log (m))
Ссылка на код (log (n) * log (m))
Реализация решения (log (n) + log (m))
Я хотел бы добавить свое объяснение к проблеме.
Это классическая проблема, когда мы должны использовать тот факт, что два массива отсортированы.
нам дали два отсортированных массива arr1 размера sz1 и arr2 размера sz2
а) Предположим, что если
Проверка, является ли k действительным
k is> (sz1 + sz2)
тогда мы не сможем найти k-й наименьший элемент в объединении обоих отсортированных массивов ryt, поэтому вернем неверные данные.
б) Теперь, если указанное выше условие имеет значение «ложь», и мы имеем действительное и допустимое значение k,
Управление граничными делами
Мы добавим оба массива по значениям -infinity в начале и + бесконечности в конце, чтобы покрыть граничные случаи k = 1,2 и k = (sz1 + sz2-1), (sz1 + sz2 ) и т.д.
Теперь оба массива имеют размер (sz1 + 2) и (sz2 + 2) соответственно
Основной алгоритм
Теперь мы выполним бинарный поиск по arr1. Мы выполним бинарный поиск по arr1 в поисках индекса i, startIndex <= i <= endIndex </strong>
такой, что если мы найдем соответствующий индекс j в arr2, используя ограничение {(i + j) = k}, то если
если (arr2 [j-1] , то arr1 [i] является k-м наименьшим (случай 1)
иначе, если (arr1 [i-1] , то arr2 [i] является k-м наименьшим (Случай 2)
else означает либо arr1 [i] (Case3)
или arr2 [j-1] (Case4)
Так как мы знаем, что k-й наименьший элемент имеет (k-1) элементов меньше его в объединении обоих массивов ryt? Таким образом,
В Case1 , что мы и сделали, мы убедились, что в arr1 [i] есть всего (k-1) меньших элементов, потому что элементы, меньшие чем arr1 [i] в массиве arr1, - это i- На 1 число больше, чем мы знаем (arr2 [j-1]
Но ответ не всегда приходит из первого массива, т.е. arr1, поэтому мы проверили case2 , который также удовлетворяет аналогично случаю 1, потому что (i-1) + (j-1) = (k-1 ) Теперь, если у нас есть (arr1 [i-1]
В case3 , чтобы сформировать его для любого из случаев 1 или 2, нам нужно увеличить i, и j будет найдено в соответствии с ограничением {(i + j) = k}, то есть в бинарном поиске переместиться в правую часть, т.е. сделать startIndex = middleIndex
В case4 , чтобы сформировать его для любого из случаев 1 или 2, нам нужно уменьшить i, и j будет найдено в соответствии с ограничением {(i + j) = k}, то есть в бинарном поиске переместиться в левую часть, т.е. сделать endIndex = middleIndex.
Теперь, как определить startIndex и endIndex в начале двоичного поиска по arr1
с startindex = 1 и endIndex = ??. Нам нужно решить.
Если k> sz1, endIndex = (sz1 + 1), иначе endIndex = k;
Потому что, если k больше, чем размер первого массива, нам, возможно, придется выполнить бинарный поиск по всему массиву arr1, иначе нам нужно только взять первые k его элементов, потому что элементы sz1-k никогда не могут внести вклад в вычисление kth наименьшего .
КОД, показанный ниже
// Complexity O(log(n)+log(m))
#include<bits/stdc++.h>
using namespace std;
#define f(i,x,y) for(int i = (x);i < (y);++i)
#define F(i,x,y) for(int i = (x);i > (y);--i)
int max(int a,int b){return (a > b?a:b);}
int min(int a,int b){return (a < b?a:b);}
int mod(int a){return (a > 0?a:((-1)*(a)));}
#define INF 1000000
int func(int *arr1,int *arr2,int sz1,int sz2,int k)
{
if((k <= (sz1+sz2))&&(k > 0))
{
int s = 1,e,i,j;
if(k > sz1)e = sz1+1;
else e = k;
while((e-s)>1)
{
i = (e+s)/2;
j = ((k-1)-(i-1));
j++;
if(j > (sz2+1)){s = i;}
else if((arr1[i] >= arr2[j-1])&&(arr1[i] <= arr2[j]))return arr1[i];
else if((arr2[j] >= arr1[i-1])&&(arr2[j] <= arr1[i]))return arr2[j];
else if(arr1[i] < arr2[j-1]){s = i;}
else if(arr1[i] > arr2[j]){e = i;}
else {;}
}
i = e,j = ((k-1)-(i-1));j++;
if((arr1[i] >= arr2[j-1])&&(arr1[i] <= arr2[j]))return arr1[i];
else if((arr2[j] >= arr1[i-1])&&(arr2[j] <= arr1[i]))return arr2[j];
else
{
i = s,j = ((k-1)-(i-1));j++;
if((arr1[i] >= arr2[j-1])&&(arr1[i] <= arr2[j]))return arr1[i];
else return arr2[j];
}
}
else
{
cout << "Data Invalid" << endl;
return -INF;
}
}
int main()
{
int n,m,k;
cin >> n >> m >> k;
int arr1[n+2];
int arr2[m+2];
f(i,1,n+1)
cin >> arr1[i];
f(i,1,m+1)
cin >> arr2[i];
arr1[0] = -INF;
arr2[0] = -INF;
arr1[n+1] = +INF;
arr2[m+1] = +INF;
int val = func(arr1,arr2,n,m,k);
if(val != -INF)cout << val << endl;
return 0;
}
Для решения сложности (log (n) * log (m))
Просто я пропустил, используя преимущество того факта, что для каждого i j можно найти, используя ограничение {(i-1) + (j-1) = (k-1)} Так что для каждого ii дополнительно применялся бинарный поиск во втором массиве найти j такой, что arr2 [j] <= arr1 [i]. Так что это решение может быть дополнительно оптимизировано </p>