O problema pede uma solução O (log (m) + log (n)) aqui. No entanto, estou dando aqui uma solução O (logK).
public class KthSmallestInTwoSortedArrays {
/ **
Problema: Encontre o k-ésimo menor de duas matrizes classificadas (comprimento m e n) combinadas
Solução: Encontre o k-ésimo menor entre os primeiros k elementos de cada array.
Usaremos a pesquisa binária aqui.
* /
/ **
- @param args
* /
public static void main (String [] args) {
int [] A = {4,5,7, 45, 67, 77, 86, 94, 101};
int [] B = {1,3,6,8,23,24,34,44,51};
int k = 6;
getKthSmallestInTwoArrays (A, B, k);
}
private static void getKthSmallestInTwoArrays (int [] a, int [] b, int k) {
int baixoA = 0, baixoB = 0, altoA = k – 1, altoB = k – 1;
if (a.length <(k – 1))
{
altoA = a.length – 1;
}
if (b.length <(k -1))
{
highB = b.length – 1;
}
if ((altoA + altoB) <k)
{
// elementos insuficientes
Retorna;
}
int midA = 0, midB = 0;
boolean canContinue = false;
resultado int = 0;
enquanto (k> = 0)
{
midA = lowA + (highA – lowA) / 2;
midB = lowB + (highB – lowB) / 2;
if (a [midA]> = b [midB])
{
// significa que os primeiros elementos midA de A são todos maiores do que os primeiros elementos midB de B
// significa que o k-ésimo menor está na segunda metade de B OU na primeira metade de A
k = k – (midB – lowB + 1);
resultado = b [midB];
altoA = médioA – 1;
lowB = midB + 1;
}
else if (a [midA] <b [midB])
{
// significa que os primeiros elementos midB de B são todos maiores do que os primeiros elementos midA de A
// significa que o k-ésimo menor está na segunda metade de A OU na primeira metade de B
k = k – (midA – lowA + 1);
resultado = a [midA];
highB = midB – 1;
lowA = midA + 1;
}
if (k == 0)
quebrar;
}
System.out.println (resultado);
}
}