¿Cómo encontrar el k-ésimo elemento más pequeño en la unión de dos matrices ordenadas?

Esta es una pregunta de tarea. Dicen que toma O(logN + logM)dónde Ny Mson las longitudes de las matrices.

Nombramos las matrices ay b. Obviamente podemos ignorar todo a[i]y b[i]donde i> k.
Primero comparemos a[k/2]y b[k/2]. Vamos b[k/2]> a[k/2]. Por tanto, podemos descartar también todosb[i] , donde i> k / 2.

Ahora tenemos todo a[i], donde i <ky todob[i] , donde i <k / 2 para encontrar la respuesta.

¿Cuál es el próximo paso?

Lo tienes, ¡sigue adelante! Y cuidado con los índices ...

Para simplificar un poco, asumiré que N y M son> k, por lo que la complejidad aquí es O (log k), que es O (log N + log M).

Pseudocódigo:

i = k/2
j = k - i
step = k/4
while step > 0
    if a[i-1] > b[j-1]
        i -= step
        j += step
    else
        i += step
        j -= step
    step /= 2

if a[i-1] > b[j-1]
    return a[i-1]
else
    return b[j-1]

Para la demostración, puede usar el invariante de bucle i + j = k, pero no haré toda su tarea :)

Espero no estar respondiendo a su tarea ya que ha pasado más de un año desde que se hizo esta pregunta. Aquí hay una solución recursiva de cola que tomará log (len (a) + len (b)) tiempo.

Supuesto: las entradas son correctas. es decir, k está en el rango [0, len (a) + len (b)]

Casos base:

• Si la longitud de una de las matrices es 0, la respuesta es el k-ésimo elemento de la segunda matriz.

Pasos de reducción:

• Si el índice medio de a+ el índice medio de bes menor quek
  • Si el elemento medio de aes mayor que el elemento medio de b, podemos ignorar la primera mitad de b, ajustark .
  • de lo contrario, ignore la primera mitad de a, ajuste k.
• De lo contrario, si kes menor que la suma de los índices medios de ayb :
  • Si el elemento medio de aes mayor que el elemento medio de b, podemos ignorar con seguridad la segunda mitad dea
  • de lo contrario, podemos ignorar la segunda mitad de b

Código:

def kthlargest(arr1, arr2, k):
    if len(arr1) == 0:
        return arr2[k]
    elif len(arr2) == 0:
        return arr1[k]

    mida1 = len(arr1)/2
    mida2 = len(arr2)/2
    if mida1+mida2<k:
        if arr1[mida1]>arr2[mida2]:
            return kthlargest(arr1, arr2[mida2+1:], k-mida2-1)
        else:
            return kthlargest(arr1[mida1+1:], arr2, k-mida1-1)
    else:
        if arr1[mida1]>arr2[mida2]:
            return kthlargest(arr1[:mida1], arr2, k)
        else:
            return kthlargest(arr1, arr2[:mida2], k)

Tenga en cuenta que mi solución es crear nuevas copias de matrices más pequeñas en cada llamada, esto se puede eliminar fácilmente pasando solo índices de inicio y finalización en las matrices originales.

Mucha gente respondió a esta pregunta del "k-ésimo elemento más pequeño de dos arreglos ordenados", pero por lo general solo con ideas generales, no con un código de trabajo claro o un análisis de condiciones de frontera.

Aquí me gustaría desarrollarlo cuidadosamente con la forma en que fui para ayudar a algunos novatos a comprender, con mi código Java que funciona correctamente. A1y A2son dos matrices ascendentes ordenadas, con size1y size2como longitud respectivamente. Necesitamos encontrar el k-ésimo elemento más pequeño de la unión de esas dos matrices. Aquí asumimos razonablemente que (k > 0 && k <= size1 + size2), lo que implica que A1yA2 no puede estar vacío a la vez.

Primero, abordemos esta pregunta con un algoritmo lento de O (k). El método consiste en comparar el primer elemento de la matriz A1[0]y A2[0]. Toma el más pequeño, di A1[0]en nuestro bolsillo. Luego compare A1[1]con A2[0], y así sucesivamente. Repite esta acción hasta que nuestro bolsillo alcance kelementos. Muy importante: En el primer paso, solo podemos comprometernos A1[0]en nuestro bolsillo. ¡NO podemos incluir ni excluir A2[0]!

El siguiente código O (k) le da un elemento antes de la respuesta correcta. Aquí lo uso para mostrar mi idea y analizar la condición de contorno. Tengo el código correcto después de este:

private E kthSmallestSlowWithFault(int k) {
    int size1 = A1.length, size2 = A2.length;

    int index1 = 0, index2 = 0;
    // base case, k == 1
    if (k == 1) {
        if (size1 == 0) {
            return A2[index2];
        } else if (size2 == 0) {
            return A1[index1];
        } else if (A1[index1].compareTo(A2[index2]) < 0) {
            return A1[index1];
        } else {
            return A2[index2];
        }
    }

    /* in the next loop, we always assume there is one next element to compare with, so we can
     * commit to the smaller one. What if the last element is the kth one?
     */
    if (k == size1 + size2) {
        if (size1 == 0) {
            return A2[size2 - 1];
        } else if (size2 == 0) {
            return A1[size1 - 1];
        } else if (A1[size1 - 1].compareTo(A2[size2 - 1]) < 0) {
            return A1[size1 - 1];
        } else {
            return A2[size2 - 1];
        }
    }

    /*
     * only when k > 1, below loop will execute. In each loop, we commit to one element, till we
     * reach (index1 + index2 == k - 1) case. But the answer is not correct, always one element
     * ahead, because we didn't merge base case function into this loop yet.
     */
    int lastElementFromArray = 0;
    while (index1 + index2 < k - 1) {
        if (A1[index1].compareTo(A2[index2]) < 0) {
            index1++;
            lastElementFromArray = 1;
            // commit to one element from array A1, but that element is at (index1 - 1)!!!
        } else {
            index2++;
            lastElementFromArray = 2;
        }
    }
    if (lastElementFromArray == 1) {
        return A1[index1 - 1];
    } else {
        return A2[index2 - 1];
    }
}

La idea más poderosa es que en cada ciclo, siempre usamos el enfoque del caso base. Después de comprometernos con el elemento más pequeño actual, nos acercamos un paso más al objetivo: el k-ésimo elemento más pequeño. ¡Nunca salte al medio y se confunda y se pierda!

Al observar el caso base del código anterior k == 1, k == size1+size2, y combinar con eso A1yA2 no pueden ser ambos vacía. Podemos convertir la lógica en un estilo más conciso a continuación.

Aquí hay un código de trabajo lento pero correcto:

private E kthSmallestSlow(int k) {
    // System.out.println("this is an O(k) speed algorithm, very concise");
    int size1 = A1.length, size2 = A2.length;

    int index1 = 0, index2 = 0;
    while (index1 + index2 < k - 1) {
        if (size1 > index1 && (size2 <= index2 || A1[index1].compareTo(A2[index2]) < 0)) {
            index1++; // here we commit to original index1 element, not the increment one!!!
        } else {
            index2++;
        }
    }
    // below is the (index1 + index2 == k - 1) base case
    // also eliminate the risk of referring to an element outside of index boundary
    if (size1 > index1 && (size2 <= index2 || A1[index1].compareTo(A2[index2]) < 0)) {
        return A1[index1];
    } else {
        return A2[index2];
    }
}

Ahora podemos probar un algoritmo más rápido que se ejecuta en O (log k). Del mismo modo, compare A1[k/2]con A2[k/2]; si A1[k/2]es más pequeño, entonces todos los elementos desde A1[0]hasta A1[k/2]deberían estar en nuestro bolsillo. La idea es no solo comprometerse con un elemento en cada ciclo; el primer paso contiene k/2elementos. Nuevamente, NO podemos incluir ni excluir A2[0]de A2[k/2]todos modos. Entonces, en el primer paso, no podemos ir más que k/2elementos. Para el segundo paso, no podemos ir más que k/4elementos ...

Después de cada paso, nos acercamos mucho más al k-ésimo elemento. Al mismo tiempo, cada paso se hace cada vez más pequeño, hasta que llegamos (step == 1), que es (k-1 == index1+index2). Entonces podemos volver a referirnos al caso base simple y poderoso.

Aquí está el código de trabajo correcto:

private E kthSmallestFast(int k) {
    // System.out.println("this is an O(log k) speed algorithm with meaningful variables name");
    int size1 = A1.length, size2 = A2.length;

    int index1 = 0, index2 = 0, step = 0;
    while (index1 + index2 < k - 1) {
        step = (k - index1 - index2) / 2;
        int step1 = index1 + step;
        int step2 = index2 + step;
        if (size1 > step1 - 1
                && (size2 <= step2 - 1 || A1[step1 - 1].compareTo(A2[step2 - 1]) < 0)) {
            index1 = step1; // commit to element at index = step1 - 1
        } else {
            index2 = step2;
        }
    }
    // the base case of (index1 + index2 == k - 1)
    if (size1 > index1 && (size2 <= index2 || A1[index1].compareTo(A2[index2]) < 0)) {
        return A1[index1];
    } else {
        return A2[index2];
    }
}

Algunas personas pueden preocuparse ¿qué (index1+index2)pasa si saltan sobre k-1? ¿Podríamos perder el caso base?(k-1 == index1+index2) ? Eso es imposible. Puedes sumar 0.5 + 0.25 + 0.125 ..., y nunca irás más allá de 1.

Por supuesto, es muy fácil convertir el código anterior en un algoritmo recursivo:

private E kthSmallestFastRecur(int k, int index1, int index2, int size1, int size2) {
    // System.out.println("this is an O(log k) speed algorithm with meaningful variables name");

    // the base case of (index1 + index2 == k - 1)
    if (index1 + index2 == k - 1) {
        if (size1 > index1 && (size2 <= index2 || A1[index1].compareTo(A2[index2]) < 0)) {
            return A1[index1];
        } else {
            return A2[index2];
        }
    }

    int step = (k - index1 - index2) / 2;
    int step1 = index1 + step;
    int step2 = index2 + step;
    if (size1 > step1 - 1 && (size2 <= step2 - 1 || A1[step1 - 1].compareTo(A2[step2 - 1]) < 0)) {
        index1 = step1;
    } else {
        index2 = step2;
    }
    return kthSmallestFastRecur(k, index1, index2, size1, size2);
}

Espero que el análisis anterior y el código Java puedan ayudarlo a comprender. ¡Pero nunca copie mi código como tarea! Salud ;)

Aquí hay una versión iterativa de C ++ de la solución de @ lambdapilgrim (vea la explicación del algoritmo allí):

#include <cassert>
#include <iterator>

template<class RandomAccessIterator, class Compare>
typename std::iterator_traits<RandomAccessIterator>::value_type
nsmallest_iter(RandomAccessIterator firsta, RandomAccessIterator lasta,
               RandomAccessIterator firstb, RandomAccessIterator lastb,
               size_t n,
               Compare less) {
  assert(issorted(firsta, lasta, less) && issorted(firstb, lastb, less));
  for ( ; ; ) {
    assert(n < static_cast<size_t>((lasta - firsta) + (lastb - firstb)));
    if (firsta == lasta) return *(firstb + n);
    if (firstb == lastb) return *(firsta + n);

    size_t mida = (lasta - firsta) / 2;
    size_t midb = (lastb - firstb) / 2;
    if ((mida + midb) < n) {
      if (less(*(firstb + midb), *(firsta + mida))) {
        firstb += (midb + 1);
        n -= (midb + 1);
      }
      else {
        firsta += (mida + 1);
        n -= (mida + 1);
      }
    }
    else {
      if (less(*(firstb + midb), *(firsta + mida)))
        lasta = (firsta + mida);
      else
        lastb = (firstb + midb);
    }
  }
}

Funciona para todos los 0 <= n < (size(a) + size(b))índices y tiene O(log(size(a)) + log(size(b)))complejidad.

Ejemplo

#include <functional> // greater<>
#include <iostream>

#define SIZE(a) (sizeof(a) / sizeof(*a))

int main() {
  int a[] = {5,4,3};
  int b[] = {2,1,0};
  int k = 1; // find minimum value, the 1st smallest value in a,b

  int i = k - 1; // convert to zero-based indexing
  int v = nsmallest_iter(a, a + SIZE(a), b, b + SIZE(b),
                         SIZE(a)+SIZE(b)-1-i, std::greater<int>());
  std::cout << v << std::endl; // -> 0
  return v;
}

Mi intento por los primeros k números, k-ésimo número en 2 matrices ordenadas y en n matrices ordenadas:

// require() is recognizable by node.js but not by browser;
// for running/debugging in browser, put utils.js and this file in <script> elements,
if (typeof require === "function") require("./utils.js");

// Find K largest numbers in two sorted arrays.
function k_largest(a, b, c, k) {
    var sa = a.length;
    var sb = b.length;
    if (sa + sb < k) return -1;
    var i = 0;
    var j = sa - 1;
    var m = sb - 1;
    while (i < k && j >= 0 && m >= 0) {
        if (a[j] > b[m]) {
            c[i] = a[j];
            i++;
            j--;
        } else {
            c[i] = b[m];
            i++;
            m--;
        }
    }
    debug.log(2, "i: "+ i + ", j: " + j + ", m: " + m);
    if (i === k) {
        return 0;
    } else if (j < 0) {
        while (i < k) {
            c[i++] = b[m--];
        }
    } else {
        while (i < k) c[i++] = a[j--];
    }
    return 0;
}

// find k-th largest or smallest number in 2 sorted arrays.
function kth(a, b, kd, dir){
    sa = a.length; sb = b.length;
    if (kd<1 || sa+sb < kd){
        throw "Mission Impossible! I quit!";
    }

    var k;
    //finding the kd_th largest == finding the smallest k_th;
    if (dir === 1){ k = kd;
    } else if (dir === -1){ k = sa + sb - kd + 1;}
    else throw "Direction has to be 1 (smallest) or -1 (largest).";

    return find_kth(a, b, k, sa-1, 0, sb-1, 0);
}

// find k-th smallest number in 2 sorted arrays;
function find_kth(c, d, k, cmax, cmin, dmax, dmin){

    sc = cmax-cmin+1; sd = dmax-dmin+1; k0 = k; cmin0 = cmin; dmin0 = dmin;
    debug.log(2, "=k: " + k +", sc: " + sc + ", cmax: " + cmax +", cmin: " + cmin + ", sd: " + sd +", dmax: " + dmax + ", dmin: " + dmin);

    c_comp = k0-sc;
    if (c_comp <= 0){
        cmax = cmin0 + k0-1;
    } else {
        dmin = dmin0 + c_comp-1;
        k -= c_comp-1;
    }

    d_comp = k0-sd;
    if (d_comp <= 0){
        dmax = dmin0 + k0-1;
    } else {
        cmin = cmin0 + d_comp-1;
        k -= d_comp-1;
    }
    sc = cmax-cmin+1; sd = dmax-dmin+1;

    debug.log(2, "#k: " + k +", sc: " + sc + ", cmax: " + cmax +", cmin: " + cmin + ", sd: " + sd +", dmax: " + dmax + ", dmin: " + dmin + ", c_comp: " + c_comp + ", d_comp: " + d_comp);

    if (k===1) return (c[cmin]<d[dmin] ? c[cmin] : d[dmin]);
    if (k === sc+sd) return (c[cmax]>d[dmax] ? c[cmax] : d[dmax]);

    m = Math.floor((cmax+cmin)/2);
    n = Math.floor((dmax+dmin)/2);

    debug.log(2, "m: " + m + ", n: "+n+", c[m]: "+c[m]+", d[n]: "+d[n]);

    if (c[m]<d[n]){
        if (m === cmax){ // only 1 element in c;
            return d[dmin+k-1];
        }

        k_next = k-(m-cmin+1);
        return find_kth(c, d, k_next, cmax, m+1, dmax, dmin);
    } else {
        if (n === dmax){
            return c[cmin+k-1];
        }

        k_next = k-(n-dmin+1);
        return find_kth(c, d, k_next, cmax, cmin, dmax, n+1);
    }
}

function traverse_at(a, ae, h, l, k, at, worker, wp){
    var n = ae ? ae.length : 0;
    var get_node;
    switch (at){
        case "k": get_node = function(idx){
                var node = {};
                var pos = l[idx] + Math.floor(k/n) - 1;
                if (pos<l[idx]){ node.pos = l[idx]; }
                else if (pos > h[idx]){ node.pos = h[idx];}
                else{ node.pos = pos; }

                node.idx = idx;
                node.val = a[idx][node.pos];
                debug.log(6, "pos: "+pos+"\nnode =");
                debug.log(6, node);
                return node;
            };
            break;
        case "l": get_node = function(idx){
                debug.log(6, "a["+idx+"][l["+idx+"]]: "+a[idx][l[idx]]);
                return a[idx][l[idx]];
            };
            break;
        case "h": get_node = function(idx){
                debug.log(6, "a["+idx+"][h["+idx+"]]: "+a[idx][h[idx]]);
                return a[idx][h[idx]];
            };
            break;
        case "s": get_node = function(idx){
                debug.log(6, "h["+idx+"]-l["+idx+"]+1: "+(h[idx] - l[idx] + 1));
                return h[idx] - l[idx] + 1;
            };
            break;
        default: get_node = function(){
                debug.log(1, "!!! Exception: get_node() returns null.");
                return null;
            };
            break;
    }

    worker.init();

    debug.log(6, "--* traverse_at() *--");

    var i;
    if (!wp){
        for (i=0; i<n; i++){
            worker.work(get_node(ae[i]));
        }    
    } else {
        for (i=0; i<n; i++){
            worker.work(get_node(ae[i]), wp);
        }
    }

    return worker.getResult();
}

sumKeeper = function(){
    var res = 0;
    return {
        init     : function(){ res = 0;},
        getResult: function(){
                debug.log(5, "@@ sumKeeper.getResult: returning: "+res);
                return res;
            },
        work     : function(node){ if (node!==null) res += node;}
    };
}();

maxPicker = function(){
    var res = null;
    return {
        init     : function(){ res = null;},
        getResult: function(){
                debug.log(5, "@@ maxPicker.getResult: returning: "+res);
                return res;
            },
        work     : function(node){
            if (res === null){ res = node;}
            else if (node!==null && node > res){ res = node;}
        }
    };    
}();

minPicker = function(){
    var res = null;
    return {
        init     : function(){ res = null;},
        getResult: function(){
                debug.log(5, "@@ minPicker.getResult: returning: ");
                debug.log(5, res);
                return res;
            },
        work     : function(node){
            if (res === null && node !== null){ res = node;}
            else if (node!==null &&
                node.val !==undefined &&
                node.val < res.val){ res = node; }
            else if (node!==null && node < res){ res = node;}
        }
    };  
}();

// find k-th smallest number in n sorted arrays;
// need to consider the case where some of the subarrays are taken out of the selection;
function kth_n(a, ae, k, h, l){
    var n = ae.length;
    debug.log(2, "------**  kth_n()  **-------");
    debug.log(2, "n: " +n+", k: " + k);
    debug.log(2, "ae: ["+ae+"],  len: "+ae.length);
    debug.log(2, "h: [" + h + "]");
    debug.log(2, "l: [" + l + "]");

    for (var i=0; i<n; i++){
        if (h[ae[i]]-l[ae[i]]+1>k) h[ae[i]]=l[ae[i]]+k-1;
    }
    debug.log(3, "--after reduction --");
    debug.log(3, "h: [" + h + "]");
    debug.log(3, "l: [" + l + "]");

    if (n === 1)
        return a[ae[0]][k-1]; 
    if (k === 1)
        return traverse_at(a, ae, h, l, k, "l", minPicker);
    if (k === traverse_at(a, ae, h, l, k, "s", sumKeeper))
        return traverse_at(a, ae, h, l, k, "h", maxPicker);

    var kn = traverse_at(a, ae, h, l, k, "k", minPicker);
    debug.log(3, "kn: ");
    debug.log(3, kn);

    var idx = kn.idx;
    debug.log(3, "last: k: "+k+", l["+kn.idx+"]: "+l[idx]);
    k -= kn.pos - l[idx] + 1;
    l[idx] = kn.pos + 1;
    debug.log(3, "next: "+"k: "+k+", l["+kn.idx+"]: "+l[idx]);
    if (h[idx]<l[idx]){ // all elements in a[idx] selected;
        //remove a[idx] from the arrays.
        debug.log(4, "All elements selected in a["+idx+"].");
        debug.log(5, "last ae: ["+ae+"]");
        ae.splice(ae.indexOf(idx), 1);
        h[idx] = l[idx] = "_"; // For display purpose only.
        debug.log(5, "next ae: ["+ae+"]");
    }

    return kth_n(a, ae, k, h, l);
}

function find_kth_in_arrays(a, k){

    if (!a || a.length<1 || k<1) throw "Mission Impossible!";

    var ae=[], h=[], l=[], n=0, s, ts=0;
    for (var i=0; i<a.length; i++){
        s = a[i] && a[i].length;
        if (s>0){
            ae.push(i); h.push(s-1); l.push(0);
            ts+=s;
        }
    }

    if (k>ts) throw "Too few elements to choose from!";

    return kth_n(a, ae, k, h, l);
}

/////////////////////////////////////////////////////
// tests
// To show everything: use 6.
debug.setLevel(1);

var a = [2, 3, 5, 7, 89, 223, 225, 667];
var b = [323, 555, 655, 673];
//var b = [99];
var c = [];

debug.log(1, "a = (len: " + a.length + ")");
debug.log(1, a);
debug.log(1, "b = (len: " + b.length + ")");
debug.log(1, b);

for (var k=1; k<a.length+b.length+1; k++){
    debug.log(1, "================== k: " + k + "=====================");

    if (k_largest(a, b, c, k) === 0 ){
      debug.log(1, "c = (len: "+c.length+")");
      debug.log(1, c);
    }

    try{
        result = kth(a, b, k, -1);
        debug.log(1, "===== The " + k + "-th largest number: " + result);
    } catch (e) {
        debug.log(0, "Error message from kth(): " + e);
    }
    debug.log("==================================================");
}

debug.log(1, "################# Now for the n sorted arrays ######################");
debug.log(1, "####################################################################");

x = [[1, 3, 5, 7, 9],
     [-2, 4, 6, 8, 10, 12],
     [8, 20, 33, 212, 310, 311, 623],
     [8],
     [0, 100, 700],
     [300],
     [],
     null];

debug.log(1, "x = (len: "+x.length+")");
debug.log(1, x);

for (var i=0, num=0; i<x.length; i++){
    if (x[i]!== null) num += x[i].length;
}
debug.log(1, "totoal number of elements: "+num);

// to test k in specific ranges:
var start = 0, end = 25;
for (k=start; k<end; k++){
    debug.log(1, "=========================== k: " + k + "===========================");

    try{
        result = find_kth_in_arrays(x, k);
        debug.log(1, "====== The " + k + "-th smallest number: " + result);
    } catch (e) {
        debug.log(1, "Error message from find_kth_in_arrays: " + e);
    }
    debug.log(1, "=================================================================");
}
debug.log(1, "x = (len: "+x.length+")");
debug.log(1, x);
debug.log(1, "totoal number of elements: "+num);

El código completo con las utilidades de depuración se puede encontrar en: https://github.com/brainclone/teasers/tree/master/kth

Aquí está mi código basado en la solución de Jules Olleon:

int getNth(vector<int>& v1, vector<int>& v2, int n)
{
    int step = n / 4;

    int i1 = n / 2;
    int i2 = n - i1;

    while(!(v2[i2] >= v1[i1 - 1] && v1[i1] > v2[i2 - 1]))
    {                   
        if (v1[i1 - 1] >= v2[i2 - 1])
        {
            i1 -= step;
            i2 += step;
        }
        else
        {
            i1 += step;
            i2 -= step;
        }

        step /= 2;
        if (!step) step = 1;
    }

    if (v1[i1 - 1] >= v2[i2 - 1])
        return v1[i1 - 1];
    else
        return v2[i2 - 1];
}

int main()  
{  
    int a1[] = {1,2,3,4,5,6,7,8,9};
    int a2[] = {4,6,8,10,12};

    //int a1[] = {1,2,3,4,5,6,7,8,9};
    //int a2[] = {4,6,8,10,12};

    //int a1[] = {1,7,9,10,30};
    //int a2[] = {3,5,8,11};
    vector<int> v1(a1, a1+9);
    vector<int> v2(a2, a2+5);


    cout << getNth(v1, v2, 5);
    return 0;  
}  

Aquí está mi implementación en C, puede consultar las explicaciones de @Jules Olléon para el algoritmo: la idea detrás del algoritmo es que mantenemos i + j = k, y encontramos tales i y j de modo que a [i-1] <b [j-1] <a [i] (o al revés). Ahora, dado que hay i elementos en 'a' más pequeños que b [j-1], y j-1 elementos en 'b' más pequeños que b [j-1], b [j-1] es el i + j-1 + 1 = k-ésimo elemento más pequeño. Para encontrar tal i, j, el algoritmo realiza una búsqueda dicotómica en las matrices.

int find_k(int A[], int m, int B[], int n, int k) {
   if (m <= 0 )return B[k-1];
   else if (n <= 0) return A[k-1];
   int i =  ( m/double (m + n))  * (k-1);
   if (i < m-1 && i<k-1) ++i;
   int j = k - 1 - i;

   int Ai_1 = (i > 0) ? A[i-1] : INT_MIN, Ai = (i<m)?A[i]:INT_MAX;
   int Bj_1 = (j > 0) ? B[j-1] : INT_MIN, Bj = (j<n)?B[j]:INT_MAX;
   if (Ai >= Bj_1 && Ai <= Bj) {
       return Ai;
   } else if (Bj >= Ai_1 && Bj <= Ai) {
       return Bj;
   }
   if (Ai < Bj_1) { // the answer can't be within A[0,...,i]
       return find_k(A+i+1, m-i-1, B, n, j);
   } else { // the answer can't be within A[0,...,i]
       return find_k(A, m, B+j+1, n-j-1, i);
   }
 }

Esta es mi solución. El código C ++ imprime el k-ésimo valor más pequeño así como el número de iteraciones para obtener el k-ésimo valor más pequeño usando un bucle, que en mi opinión está en el orden de log (k). Sin embargo, el código requiere que k sea menor que la longitud de la primera matriz, lo cual es una limitación.

#include <iostream>
#include <vector>
#include<math.h>
using namespace std;

template<typename comparable>
comparable kthSmallest(vector<comparable> & a, vector<comparable> & b, int k){

int idx1; // Index in the first array a
int idx2; // Index in the second array b
comparable maxVal, minValPlus;
float iter = k;
int numIterations = 0;

if(k > a.size()){ // Checks if k is larger than the size of first array
    cout << " k is larger than the first array" << endl;
    return -1;
}
else{ // If all conditions are satisfied, initialize the indexes
    idx1 = k - 1;
    idx2 = -1;
}

for ( ; ; ){
    numIterations ++;
    if(idx2 == -1 || b[idx2] <= a[idx1] ){
        maxVal = a[idx1];
        minValPlus = b[idx2 + 1];
        idx1 = idx1 - ceil(iter/2); // Binary search
        idx2 = k - idx1 - 2; // Ensures sum of indices  = k - 2
    }
    else{
        maxVal = b[idx2];
        minValPlus = a[idx1 + 1];
        idx2 = idx2 - ceil(iter/2); // Binary search
        idx1 = k - idx2 - 2; // Ensures sum of indices  = k - 2
    }
    if(minValPlus >= maxVal){ // Check if kth smallest value has been found
        cout << "The number of iterations to find the " << k << "(th) smallest value is    " << numIterations << endl;
        return maxVal;

    }
    else
        iter/=2; // Reduce search space of binary search
   }
}

int main(){
//Test Cases
    vector<int> a = {2, 4, 9, 15, 22, 34, 45, 55, 62, 67, 78, 85};
    vector<int> b = {1, 3, 6, 8, 11, 13, 15, 20, 56, 67, 89};
    // Input k < a.size()
    int kthSmallestVal;
    for (int k = 1; k <= a.size() ; k++){
        kthSmallestVal = kthSmallest<int>( a ,b ,k );
        cout << k <<" (th) smallest Value is " << kthSmallestVal << endl << endl << endl;
    }
}

El primer pseudocódigo proporcionado anteriormente no funciona para muchos valores. Por ejemplo, aquí hay dos matrices. int [] a = {1, 5, 6, 8, 9, 11, 15, 17, 19}; int [] b = {4, 7, 8, 13, 15, 18, 20, 24, 26};

No funcionó para k = 3 y k = 9 en él. Tengo otra solucion Se da a continuación.

private static void traverse(int pt, int len) {
int temp = 0;

if (len == 1) {
    int val = 0;
    while (k - (pt + 1) - 1 > -1 && M[pt] < N[k - (pt + 1) - 1]) {

    if (val == 0)
        val = M[pt] < N[k - (pt + 1) - 1] ? N[k - (pt + 1) - 1]
            : M[pt];
    else {
        int t = M[pt] < N[k - (pt + 1) - 1] ? N[k - (pt + 1) - 1]
            : M[pt];
        val = val < t ? val : t;

    }

    ++pt;
    }

    if (val == 0)
    val = M[pt] < N[k - (pt + 1) - 1] ? N[k - (pt + 1) - 1] : M[pt];

    System.out.println(val);
    return;
}

temp = len / 2;

if (M[pt + temp - 1] < N[k - (pt + temp) - 1]) {
    traverse(pt + temp, temp);

} else {
    traverse(pt, temp);
}

}

Pero ... tampoco funciona para k = 5. Existe esta captura par / impar de k que no deja que sea simple.

public class KthSmallestInSortedArray {

    public static void main(String[] args) {
        int a1[] = {2, 3, 10, 11, 43, 56},
                a2[] = {120, 13, 14, 24, 34, 36},
                k = 4;

        System.out.println(findKthElement(a1, a2, k));

    }

    private static int findKthElement(int a1[], int a2[], int k) {

        /** Checking k must less than sum of length of both array **/
        if (a1.length + a2.length < k) {
            throw new IllegalArgumentException();
        }

        /** K must be greater than zero **/
        if (k <= 0) {
            throw new IllegalArgumentException();
        }

        /**
         * Finding begin, l and end such that
         * begin <= l < end
         * a1[0].....a1[l-1] and
         * a2[0]....a2[k-l-1] are the smallest k numbers
         */
        int begin = Math.max(0, k - a2.length);
        int end = Math.min(a1.length, k);

        while (begin < end) {
            int l = begin + (end - begin) / 2;

            /** Can we include a1[l] in the k smallest numbers */
            if ((l < a1.length) &&
                    (k - l > 0) &&
                    (a1[l] < a2[k - l - 1])) {

                begin = l + 1;

            } else if ((l > 0) &&
                    (k - l < a2.length) &&
                    (a1[l - 1] > a2[k - 1])) {

                /**
                 * This is the case where we can discard
                 * a[l-1] from the set of k smallest numbers
                 */
                end = l;

            } else {

                /**
                 * We found our answer since both inequalities were
                 * false
                 */
                begin = l;
                break;
            }
        }

        if (begin == 0) {
            return a2[k - 1];
        } else if (begin == k) {
            return a1[k - 1];
        } else {
            return Math.max(a1[begin - 1], a2[k - begin - 1]);
        }
    }
}

Aquí está la solución mía en java. Intentará optimizarlo aún más

  public class FindKLargestTwoSortedArray {

    public static void main(String[] args) {
        int[] arr1 = { 10, 20, 40, 80 };
        int[] arr2 = { 15, 35, 50, 75 };

    FindKLargestTwoSortedArray(arr1, 0, arr1.length - 1, arr2, 0,
            arr2.length - 1, 6);
    }


    public static void FindKLargestTwoSortedArray(int[] arr1, int start1,
            int end1, int[] arr2, int start2, int end2, int k) {

        if ((start1 <= end1 && start1 >= 0 && end1 < arr1.length)
                && (start2 <= end2 && start2 >= 0 && end2 < arr2.length)) {

            int midIndex1 = (start1 + (k - 1) / 2);
            midIndex1 = midIndex1 >= arr1.length ? arr1.length - 1 : midIndex1;
            int midIndex2 = (start2 + (k - 1) / 2);
            midIndex2 = midIndex2 >= arr2.length ? arr2.length - 1 : midIndex2;


            if (arr1[midIndex1] == arr2[midIndex2]) {
                System.out.println("element is " + arr1[midIndex1]);
            } else if (arr1[midIndex1] < arr2[midIndex2]) {

                if (k == 1) {
                    System.out.println("element is " + arr1[midIndex1]);
                    return;
                } else if (k == 2) {
                    System.out.println("element is " + arr2[midIndex2]);
                    return;
                }else if (midIndex1 == arr1.length-1 || midIndex2 == arr2.length-1 ) {
                    if(k==(arr1.length+arr2.length)){
                    System.out.println("element is " + arr2[midIndex2]);
                    return;
                    }else if(k==(arr1.length+arr2.length)-1){
                        System.out.println("element is " + arr1[midIndex1]);
                        return;
                    }

                }

                int remainingElementToSearch = k - (midIndex1-start1);
                FindKLargestTwoSortedArray(
                        arr1,
                        midIndex1,
                        (midIndex1 + remainingElementToSearch) >= arr1.length ? arr1.length-1
                                : (midIndex1 + remainingElementToSearch), arr2,
                        start2, midIndex2, remainingElementToSearch);

            } else if (arr1[midIndex1] > arr2[midIndex2]) {
                FindKLargestTwoSortedArray(arr2, start2, end2, arr1, start1,
                        end1, k);
            }

        } else {
            return;
        }

    }
}

Esto está inspirado en Algo en un maravilloso video de youtube

Enlace a la complejidad del código (log (n) + log (m))

Enlace al código (log (n) * log (m))

Implementación de la solución (log (n) + log (m))

Me gustaría agregar mi explicación al problema. Este es un problema clásico en el que tenemos que utilizar el hecho de que las dos matrices están ordenadas. se nos han dado dos matrices ordenadas arr1 de tamaño sz1 y arr2 de tamaño sz2

a) Supongamos que si

Comprobando si k es válido

k es> (sz1 + sz2)

entonces no podemos encontrar el k-ésimo elemento más pequeño en la unión de ambas matrices ordenadas ryt Entonces devuelve datos no válidos. b) Ahora, si la condición anterior es falsa y tenemos un valor válido y factible de k,

Gestión de casos periféricos

Agregaremos tanto las matrices por valores -infinito al principio como valores + infinito al final para cubrir los casos extremos de k = 1,2 y k = (sz1 + sz2-1), (sz1 + sz2), etc.

Ahora ambas matrices tienen tamaño (sz1 + 2) y (sz2 + 2) respectivamente

Algoritmo principal

Ahora, haremos una búsqueda binaria en arr1. Haremos una búsqueda binaria en arr1 buscando un índice i, startIndex <= i <= endIndex

tal que si encontramos el índice j correspondiente en arr2 usando la restricción {(i + j) = k}, entonces si

si (arr2 [j-1] <arr1 [i] <arr2 [j]) , entonces arr1 [i] es el k-ésimo más pequeño (Caso 1)

de lo contrario, si (arr1 [i-1] <arr2 [j] <arr1 [i]) , entonces arr2 [i] es el k-ésimo más pequeño (Caso 2)

else significa arr1 [i] <arr2 [j-1] <arr2 [j] (Case3)

o arr2 [j-1] <arr2 [j] <arr1 [i] (Case4)

Como sabemos que el k-ésimo elemento más pequeño tiene (k-1) elementos más pequeños que él en la unión de ambas matrices ryt? Entonces,

En el caso 1 , lo que hicimos, nos aseguramos de que haya un total de (k-1) elementos más pequeños en arr1 [i] porque los elementos más pequeños que arr1 [i] en la matriz arr1 son i-1 en número de lo que sabemos (arr2 [ j-1] <arr1 [i] <arr2 [j]) y el número de elementos menores que arr1 [i] en arr2 es j-1 porque j se encuentra usando (i-1) + (j-1) = (k -1) Entonces el k-ésimo elemento más pequeño será arr1 [i]

Pero la respuesta no siempre puede provenir de la primera matriz, es decir, arr1, por lo que verificamos el caso2, que también satisface de manera similar al caso 1 porque (i-1) + (j-1) = (k-1). Ahora, si tenemos (arr1 [i-1] <arr2 [j] <arr1 [i]) tenemos un total de k-1 elementos más pequeños que arr2 [j] en unión de ambos arreglos, por lo que es el k-ésimo elemento más pequeño.

en case3 , para formar a cualquiera de caso 1 o el caso 2, es necesario para incrementar i y j se encontrará según el uso de restricción {(i + j) = k} es decir, en la búsqueda binaria movimiento para parte derecha es decir, hacer startIndex = middleIndex

En el caso 4 , para formarlo en cualquiera de los casos 1 o 2, necesitamos disminuir i y j se encontrarán de acuerdo con la restricción {(i + j) = k} es decir, en la búsqueda binaria, mover a la parte izquierda, es decir, hacer endIndex = middleIndex .

Ahora, ¿cómo decidir startIndex y endIndex al comienzo de la búsqueda binaria sobre arr1 con startindex = 1 y endIndex = ??. Tenemos que decidir.

Si k> sz1, endIndex = (sz1 + 1), de lo contrario endIndex = k;

Porque si k es mayor que el tamaño de la primera matriz, es posible que tengamos que hacer una búsqueda binaria en toda la matriz arr1; de lo contrario, solo necesitamos tomar los primeros k elementos porque sz1-k elementos nunca pueden contribuir en el cálculo de la k-ésima menor.

CÓDIGO mostrado a continuación

// 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;

}

Para Solución de complejidad (log (n) * log (m))

Simplemente no aproveché la ventaja del hecho de que para cada i, el j se puede encontrar usando la restricción {(i-1) + (j-1) = (k-1)} Entonces, para cada ii se aplicó una búsqueda binaria en la segunda matriz para encontrar j tal que arr2 [j] <= arr1 [i]. Entonces esta solución se puede optimizar aún más

Básicamente, a través de este enfoque, puede descartar k / 2 elementos en cada paso. La K cambiará recursivamente de k => k / 2 => k / 4 => ... hasta que llegue a 1. Entonces, la complejidad del tiempo es O (logk)

En k = 1, obtenemos la más baja de las dos matrices.

El siguiente código está en JAVA. Tenga en cuenta que estamos restando 1 (-1) en el código de los índices porque el índice de la matriz de Java comienza en 0 y no en 1, por ejemplo. k = 3 está representado por el elemento en el segundo índice de una matriz.

private int kthElement(int[] arr1, int[] arr2, int k) {
        if (k < 1 || k > (arr1.length + arr2.length))
            return -1;
        return helper(arr1, 0, arr1.length - 1, arr2, 0, arr2.length - 1, k);
    }


private int helper(int[] arr1, int low1, int high1, int[] arr2, int low2, int high2, int k) {
    if (low1 > high1) {
        return arr2[low2 + k - 1];
    } else if (low2 > high2) {
        return arr1[low1 + k - 1];
    }
    if (k == 1) {
        return Math.min(arr1[low1], arr2[low2]);
    }
    int i = Math.min(low1 + k / 2, high1 + 1);
    int j = Math.min(low2 + k / 2, high2 + 1);
    if (arr1[i - 1] > arr2[j - 1]) {
        return helper(arr1, low1, high1, arr2, j, high2, k - (j - low2));
    } else {
        return helper(arr1, i, high1, arr2, low2, high2, k - (i - low1));
    }
}

#include <bits/stdc++.h>
using namespace std;

int findKthElement(int a[],int start1,int end1,int b[],int start2,int end2,int k){

    if(start1 >= end1)return b[start2+k-1];
    if(start2 >= end2)return a[start1+k-1];
    if(k==1)return min(a[start1],b[start2]);
    int aMax = INT_MAX;
    int bMax = INT_MAX;
    if(start1+k/2-1 < end1) aMax = a[start1 + k/2 - 1];
    if(start2+k/2-1 < end2) bMax = b[start2 + k/2 - 1];

    if(aMax > bMax){
        return findKthElement(a,start1,end1,b,start2+k/2,end2,k-k/2);
    }
    else{
        return findKthElement(a,start1 + k/2,end1,b,start2,end2,k-k/2);
    }
}

int main(void){
    int t;
    scanf("%d",&t);
    while(t--){
        int n,m,k;
        cout<<"Enter the size of 1st Array"<<endl;
        cin>>n;
        int arr[n];
        cout<<"Enter the Element of 1st Array"<<endl;
        for(int i = 0;i<n;i++){
            cin>>arr[i];
        }
        cout<<"Enter the size of 2nd Array"<<endl;
        cin>>m;
        int arr1[m];
        cout<<"Enter the Element of 2nd Array"<<endl;
        for(int i = 0;i<m;i++){
            cin>>arr1[i];
        }
        cout<<"Enter The Value of K";
        cin>>k;
        sort(arr,arr+n);
        sort(arr1,arr1+m);
        cout<<findKthElement(arr,0,n,arr1,0,m,k)<<endl;
    }

    return 0;
}

La complejidad del tiempo es O (log (min (n, m)))

La mayoría de las respuestas que encontré aquí se centran en ambas matrices. si bien es bueno, pero es más difícil de implementar, ya que hay muchos casos extremos de los que debemos ocuparnos. Además de que la mayoría de las implementaciones son recursivas, lo que agrega la complejidad espacial de la pila de recursividad. Entonces, en lugar de enfocarme en ambas matrices, decidí enfocarme solo en la matriz más pequeña y hacer la búsqueda binaria solo en la matriz más pequeña y ajustar el puntero para la segunda matriz en función del valor del puntero en la primera matriz. Mediante la siguiente aplicación, tenemos la complejidad de O(log(min(n,m))la O(1)complejidad del espacio.

    public static int kth_two_sorted(int []a, int b[],int k){
    if(a.length > b.length){
        return kth_two_sorted(b,a,k);
    }
    if(a.length + a.length < k){
        throw new RuntimeException("wrong argument");
    }
    int low = 0;
    int high = k;
    if(a.length <= k){
        high = a.length-1;
    }
    while(low <= high){
        int sizeA = low+(high - low)/2;
        int sizeB = k - sizeA;
        boolean shrinkLeft = false;
        boolean extendRight = false;
        if(sizeA != 0){
            if(sizeB !=b.length){
                if(a[sizeA-1] > b[sizeB]){
                    shrinkLeft = true;
                    high = sizeA-1;
                }
            }
        }
        if(sizeA!=a.length){
            if(sizeB!=0){
                if(a[sizeA] < b[sizeB-1]){
                    extendRight = true;
                    low = sizeA;
                }
            }
        }
        if(!shrinkLeft && !extendRight){
            return Math.max(a[sizeA-1],b[sizeB-1]) ;
        }
    }
    throw  new IllegalArgumentException("we can't be here");
}

Tenemos un rango de [low, high]for array ay estrechamos este rango a medida que avanzamos en el algoritmo. sizeAmuestra cuántos elementos de los kelementos son de la matriz ay se deriva del valor de lowy high. sizeBes la misma definición excepto que calculamos el valor de tal manera quesizeA+sizeB=k . El basado en los valores en esos dos bordes concluye que tenemos que extendernos hacia el lado derecho en una matriz ao encogernos hacia el lado izquierdo. si nos limitamos en la misma posición que significa que hemos encontrado la solución y se remitirá el máximo de los valores en la posición de sizeA-1partir ay sizeB-1desde b.

Verifique este código.

import math
def findkthsmallest():

    A=[1,5,10,22,30,35,75,125,150,175,200]
    B=[15,16,20,22,25,30,100,155,160,170]
    lM=0
    lN=0
    hM=len(A)-1
    hN=len(B)-1
    k=17

    while True:
        if k==1:
            return min(A[lM],B[lN])


        cM=hM-lM+1
        cN=hN-lN+1
        tmp = cM/float(cM+cN)
        iM=int(math.ceil(tmp*k))
        iN=k-iM
        iM=lM+iM-1
        iN=lN+iN-1
        if A[iM] >= B[iN]:
            if iN == hN or A[iM] < B[iN+1]:
                return A[iM]
            else:
                k = k - (iN-lN+1)
                lN=iN+1
                hM=iM-1
        if B[iN] >= A[iM]:
            if iM == hM or B[iN] < A[iM+1]:
                return B[iN]
            else:
                k = k - (iM-lM+1)
                lM=iM+1
                hN=iN-1
        if hM < lM:
            return B[lN+k-1]
        if hN < lN:
            return A[lM+k-1]

if __name__ == '__main__':
    print findkthsmallest();

Debajo del código C # para encontrar el k-ésimo elemento más pequeño en la unión de dos matrices ordenadas. Complejidad de tiempo: O (logk)

        public static int findKthSmallestElement1(int[] A, int startA, int endA, int[] B, int startB, int endB, int k)
        {
            int n = endA - startA;
            int m = endB - startB;

            if (n <= 0)
                return B[startB + k - 1];
            if (m <= 0)
                return A[startA + k - 1];
            if (k == 1)
                return A[startA] < B[startB] ? A[startA] : B[startB];

            int midA = (startA + endA) / 2;
            int midB = (startB + endB) / 2;

            if (A[midA] <= B[midB])
            {
                if (n / 2 + m / 2 + 1 >= k)
                    return findKthSmallestElement1(A, startA, endA, B, startB, midB, k);
                else
                    return findKthSmallestElement1(A, midA + 1, endA, B, startB, endB, k - n / 2 - 1);
            }
            else
            {
                if (n / 2 + m / 2 + 1 >= k)
                    return findKthSmallestElement1(A, startA, midA, B, startB, endB, k);
                else
                    return findKthSmallestElement1(A, startA, endA, B, midB + 1, endB, k - m / 2 - 1);

            }
        }