Comment trouver le kième élément le plus petit dans l'union de deux tableaux triés?

C'est une question de devoir. Ils disent que cela prend O(logN + logM)où Net Msont les longueurs des tableaux.

Appelons les tableaux aet b. De toute évidence, nous pouvons ignorer tout a[i]et b[i]où i> k.
Commençons par comparer a[k/2]et b[k/2]. Soit b[k/2]> a[k/2]. Par conséquent, nous pouvons également tout rejeter b[i], où i> k / 2.

Nous avons maintenant tout a[i], où i <k et tout b[i], où i <k / 2 pour trouver la réponse.

Quelle est la prochaine étape?

Vous l'avez, continuez! Et soyez prudent avec les index ...

Pour simplifier un peu, je suppose que N et M sont> k, donc la complexité ici est O (log k), qui est O (log N + log M).

Pseudo-code:

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]

Pour la démonstration, vous pouvez utiliser l'invariant de boucle i + j = k, mais je ne ferai pas tous vos devoirs :)

J'espère que je ne réponds pas à vos devoirs car cela fait plus d'un an que cette question a été posée. Voici une solution récursive de queue qui prendra du temps de log (len (a) + len (b)).

Hypothèse: les entrées sont correctes. c'est-à-dire que k est compris entre [0, len (a) + len (b)]

Cas de base:

• Si la longueur de l'un des tableaux est égale à 0, la réponse est le kème élément du deuxième tableau.

Étapes de réduction:

• Si l'indice moyen de a+ l'indice moyen de best inférieur àk
  • Si l'élément milieu de aest supérieur à l'élément milieu de b, nous pouvons ignorer la première moitié de b, ajustez k.
  • sinon ignorer la première moitié de a, ajuster k.
• Sinon si kest inférieur à la somme des indices intermédiaires de aet b:
  • Si l'élément milieu de aest supérieur à l'élément milieu de b, nous pouvons ignorer en toute sécurité la seconde moitié dea
  • sinon nous pouvons ignorer la seconde moitié de b

Code:

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)

Veuillez noter que ma solution crée de nouvelles copies de tableaux plus petits à chaque appel, cela peut être facilement éliminé en ne passant que les index de début et de fin sur les tableaux d'origine.

Beaucoup de gens ont répondu à cette question «ke plus petit élément de deux tableaux triés», mais généralement avec seulement des idées générales, pas un code de travail clair ou une analyse des conditions aux limites.

Ici, je voudrais l'élaborer soigneusement avec la façon dont je suis allé pour aider certains novices à comprendre, avec mon code Java fonctionnel. A1et A2sont deux tableaux ascendants triés, avec size1et size2comme longueur respectivement. Nous devons trouver le k-ème plus petit élément de l'union de ces deux tableaux. Ici, nous supposons raisonnablement cela (k > 0 && k <= size1 + size2), ce qui implique cela A1et A2ne peut pas être à la fois vide.

Tout d'abord, abordons cette question avec un algorithme lent O (k). La méthode consiste à comparer le premier élément des deux tableaux, A1[0]et A2[0]. Prenez le plus petit, dites A1[0]-le dans notre poche. Ensuite, comparez A1[1]avec A2[0], et ainsi de suite. Répétez cette action jusqu'à ce que notre poche atteigne les kéléments. Très important: dans la première étape, nous ne pouvons nous engager que A1[0]dans notre poche. Nous ne pouvons PAS inclure ou exclure A2[0]!!!

Le code O (k) suivant vous donne un élément avant la bonne réponse. Ici, je l'utilise pour montrer mon idée et la condition aux limites de l'analyse. J'ai le code correct après celui-ci:

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];
    }
}

L'idée la plus puissante est que dans chaque boucle, nous utilisons toujours l'approche du cas de base. Après nous être engagés sur le plus petit élément actuel, nous nous rapprochons de la cible: le k-ème plus petit élément. Ne sautez jamais au milieu et soyez confus et perdu!

En observant le cas de base du code ci-dessus k == 1, k == size1+size2, et combinez-le avec cela A1et A2ne peut pas être les deux vides. Nous pouvons transformer la logique en un style plus concis ci-dessous.

Voici un code de travail lent mais correct:

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];
    }
}

Nous pouvons maintenant essayer un algorithme plus rapide fonctionnant à O (log k). De même, comparez A1[k/2]avec A2[k/2]; si A1[k/2]est plus petit, alors tous les éléments de A1[0]à A1[k/2]devraient être dans notre poche. L'idée est de ne pas simplement s'engager sur un élément dans chaque boucle; la première étape contient des k/2éléments. Encore une fois, nous ne pouvons PAS inclure ou exclure A2[0]de A2[k/2]toute façon. Donc, dans un premier temps, nous ne pouvons pas aller plus loin que des k/2éléments. Pour la deuxième étape, on ne peut pas aller plus que des k/4éléments ...

Après chaque étape, nous nous rapprochons beaucoup plus du k-ème élément. En même temps, chaque pas devient de plus en plus petit, jusqu'à ce que nous atteignions (step == 1)ce qui est (k-1 == index1+index2). Ensuite, nous pouvons à nouveau nous référer au cas de base simple et puissant.

Voici le code correct de fonctionnement:

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];
    }
}

Certaines personnes peuvent s'inquiéter si (index1+index2)sauter par-dessus k-1? Pouvons-nous manquer le cas de base (k-1 == index1+index2)? C'est impossible. Vous pouvez additionner 0,5 + 0,25 + 0,125 ..., et vous n'irez jamais au-delà de 1.

Bien sûr, il est très facile de transformer le code ci-dessus en algorithme récursif:

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);
}

J'espère que l'analyse ci-dessus et le code Java pourront vous aider à comprendre. Mais ne copiez jamais mon code comme devoirs! À votre santé ;)

Voici une version itérative C ++ de la solution de @ lambdapilgrim (voir l'explication de l'algorithme ici):

#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);
    }
  }
}

Cela fonctionne pour tous les 0 <= n < (size(a) + size(b))index et est O(log(size(a)) + log(size(b)))complexe.

Exemple

#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;
}

Ma tentative pour les k premiers nombres, le kième nombre dans 2 tableaux triés et dans n tableaux triés:

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

Le code complet avec les utilitaires de débogage peut être trouvé à: https://github.com/brainclone/teasers/tree/master/kth

Voici mon code basé sur la solution 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;  
}  

Voici mon implémentation en C, vous pouvez vous référer aux explications de @Jules Olléon pour l'algorithme: l'idée derrière l'algorithme est que nous maintenons i + j = k, et trouvons ces i et j pour que a [i-1] <b [j-1] <a [i] (ou inversement). Maintenant, puisqu'il y a i éléments dans 'a' plus petits que b [j-1], et j-1 éléments dans 'b' plus petits que b [j-1], b [j-1] est le i + j-1 + 1 = kème plus petit élément. Pour trouver un tel i, j, l'algorithme effectue une recherche dichotomique sur les tableaux.

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);
   }
 }

Voici ma solution. Le code C ++ imprime la kème plus petite valeur ainsi que le nombre d'itérations pour obtenir la kème plus petite valeur en utilisant une boucle, ce qui à mon avis est de l'ordre de log (k). Le code exige cependant que k soit plus petit que la longueur du premier tableau, ce qui est une limitation.

#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;
    }
}

Le premier pseudo code fourni ci-dessus ne fonctionne pas pour de nombreuses valeurs. Par exemple, voici deux tableaux. int [] a = {1, 5, 6, 8, 9, 11, 15, 17, 19}; int [] b = {4, 7, 8, 13, 15, 18, 20, 24, 26};

Cela n'a pas fonctionné pour k = 3 et k = 9. J'ai une autre solution. Il est donné ci-dessous.

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);
}

}

Mais ... cela ne fonctionne pas non plus pour k = 5. Il y a cette prise paire / impaire de k qui ne le laisse pas 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]);
        }
    }
}

Voici ma solution en java. Essaiera de l'optimiser davantage

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

    }
}

Ceci est inspiré d'Algo à la merveilleuse vidéo youtube

Lien vers la complexité du code (log (n) + log (m))

Lien vers le code (log (n) * log (m))

Implémentation de la solution (log (n) + log (m))

Je voudrais ajouter mon explication au problème. Il s'agit d'un problème classique où nous devons utiliser le fait que les deux tableaux sont triés. on nous a donné deux tableaux triés arr1 de taille sz1 et arr2 de taille sz2

a) Supposons si

Vérifier si k est valide

k est> (sz1 + sz2)

alors nous ne pouvons pas trouver le kème plus petit élément dans l'union des deux tableaux triés ryt Donc, retournez des données invalides. b) Maintenant, si la condition ci-dessus est fausse et que nous avons une valeur valide et faisable de k,

Gestion des cas Edge

Nous ajouterons les deux tableaux par des valeurs -infinity au début et + des valeurs infinies à la fin pour couvrir les cas de bord de k = 1,2 et k = (sz1 + sz2-1), (sz1 + sz2) etc.

Or , les tableaux ont une taille (SZ1 + 2) et (SZ2 + 2) respectivement

Algorithme principal

Maintenant, nous allons faire une recherche binaire sur arr1. Nous allons faire une recherche binaire sur arr1 à la recherche d'un index i, startIndex <= i <= endIndex

tel que si nous trouvons l'index correspondant j dans arr2 en utilisant la contrainte {(i + j) = k}, alors si

if (arr2 [j-1] <arr1 [i] <arr2 [j]) , alors arr1 [i] est le kième plus petit (cas 1)

sinon si (arr1 [i-1] <arr2 [j] <arr1 [i]) , alors arr2 [i] est le kième plus petit (cas 2)

else signifie soit arr1 [i] <arr2 [j-1] <arr2 [j] (Cas3)

ou arr2 [j-1] <arr2 [j] <arr1 [i] (Cas 4)

Puisque nous savons que le kème élément le plus petit a (k-1) éléments plus petits que lui en union des deux tableaux ryt? Alors,

Dans le cas 1 , ce que nous avons fait, nous nous sommes assurés qu'il y avait un total de (k-1) éléments plus petits à arr1 [i] parce que les éléments plus petits que arr1 [i] dans le tableau arr1 sont i-1 en nombre que nous savons (arr2 [ j-1] <arr1 [i] <arr2 [j]) et le nombre d'éléments plus petit que arr1 [i] dans arr2 est j-1 car j est trouvé en utilisant (i-1) + (j-1) = (k -1) Donc le kième élément le plus petit sera arr1 [i]

Mais la réponse peut ne pas toujours provenir du premier tableau, c'est-à-dire arr1, donc nous avons vérifié le cas2 qui satisfait également de la même manière que le cas 1 car (i-1) + (j-1) = (k-1). Maintenant, si nous avons (arr1 [i-1] <arr2 [j] <arr1 [i]) nous avons un total de k-1 éléments plus petits que arr2 [j] dans l'union des deux tableaux, donc c'est le kème élément le plus petit.

Dans le cas 3 , pour le former à l'un des cas 1 ou 2, nous devons incrémenter i et j sera trouvé en utilisant la contrainte {(i + j) = k} c'est-à-dire dans la recherche binaire, déplacez-vous vers la partie droite, c'est-à-dire faites startIndex = middleIndex

Dans le cas 4 , pour le former à l'un des cas 1 ou 2, nous devons décrémenter i et j sera trouvé en utilisant la contrainte {(i + j) = k} c'est-à-dire dans la recherche binaire se déplacer vers la partie gauche, c'est-à-dire faire endIndex = middleIndex .

Maintenant, comment décider de startIndex et endIndex au début de la recherche binaire sur arr1 avec startindex = 1 et endIndex = ??. Nous devons décider.

Si k> sz1, endIndex = (sz1 + 1), sinon endIndex = k;

Parce que si k est supérieur à la taille du premier tableau, nous pouvons avoir à faire une recherche binaire sur tout le tableau arr1, sinon nous devons seulement en prendre les k premiers éléments, car les éléments sz1-k ne peuvent jamais contribuer au calcul du kème plus petit.

CODE illustré ci-dessous

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

}

Pour Solution de complexité (log (n) * log (m))

J'ai juste manqué d'utiliser l'avantage du fait que pour chaque i, le j peut être trouvé en utilisant la contrainte {(i-1) + (j-1) = (k-1)} Donc, pour chaque ii, on appliquait davantage la recherche binaire sur le deuxième tableau pour trouver j tel que arr2 [j] <= arr1 [i] .Cette solution peut donc être optimisée davantage

Fondamentalement, via cette approche, vous pouvez supprimer k / 2 éléments à chaque étape. Le K changera récursivement de k => k / 2 => k / 4 => ... jusqu'à ce qu'il atteigne 1. Ainsi, la complexité temporelle est O (logk)

À k = 1, nous obtenons le plus bas des deux tableaux.

Le code suivant est en JAVA. Veuillez noter que nous soustrayons 1 (-1) dans le code des indices car l'index du tableau Java commence à 0 et non à 1, par exemple. k = 3 est représenté par l'élément dans le 2ème index d'un tableau.

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 complexité du temps est O (log (min (n, m)))

La plupart des réponses que j'ai trouvées ici se concentrent sur les deux tableaux. bien que ce soit bien, mais c'est plus difficile à mettre en œuvre car il y a beaucoup de cas extrêmes dont nous devons nous occuper. En outre, la plupart des implémentations sont récursives, ce qui ajoute la complexité spatiale de la pile de récursivité. Donc, au lieu de me concentrer sur les deux tableaux, j'ai décidé de me concentrer uniquement sur le plus petit tableau et de faire la recherche binaire uniquement sur le plus petit tableau et d'ajuster le pointeur du deuxième tableau en fonction de la valeur du pointeur dans le premier tableau. Par la mise en œuvre suivante, nous avons la complexité O(log(min(n,m))avec la O(1)complexité de l' espace.

    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");
}

Nous avons une plage de [low, high]tableaux pour aet nous réduisons cette plage au fur et à mesure que nous progressons dans l'algorithme. sizeAmontre combien d'éléments des kéléments proviennent du tableau aet dérive de la valeur de lowet high. sizeBest la même définition sauf que nous calculons la valeur de telle manière que sizeA+sizeB=k. Le basé sur les valeurs de ces deux bordures concluent que nous devons étendre vers le côté droit dans le tableau aou réduire vers le côté gauche. si nous coincés dans la même position , cela signifie que nous avons trouvé la solution et nous retournerons au maximum de valeurs dans la position à sizeA-1partir aet à sizeB-1partir b.

Vérifiez ce code.

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();

Sous le code C # pour trouver le k-ième élément le plus petit de l'union de deux tableaux triés. Complexité temporelle: 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);

            }
        }