Bagaimana menemukan elemen terkecil ke-k dalam gabungan dua larik yang diurutkan?

Ini adalah pertanyaan pekerjaan rumah. Mereka mengatakan itu mengambil di O(logN + logM)mana Ndan Mpanjang lariknya.

Mari beri nama array adan b. Jelas kita bisa mengabaikan semua a[i]dan di b[i]mana i> k.
Pertama mari kita bandingkan a[k/2]dan b[k/2]. Biarkan b[k/2]> a[k/2]. Oleh karena itu kita dapat membuang juga semua b[i], dimana i> k / 2.

Sekarang kita memiliki semua a[i], di mana i <k dan semua b[i], di mana i <k / 2 untuk menemukan jawabannya.

Apa langkah selanjutnya?

Anda mengerti, lanjutkan saja! Dan hati-hati dengan indeks ...

Untuk menyederhanakannya, saya akan berasumsi bahwa N dan M adalah> k, jadi kompleksitasnya di sini adalah O (log k), yaitu O (log N + log M).

Kode semu:

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]

Untuk demonstrasi Anda dapat menggunakan invarian loop i + j = k, tetapi saya tidak akan melakukan semua pekerjaan rumah Anda :)

Saya harap saya tidak menjawab pekerjaan rumah Anda karena sudah lebih dari setahun sejak pertanyaan ini diajukan. Berikut adalah solusi rekursif ekor yang akan membutuhkan waktu log (len (a) + len (b)).

Asumsi: Masukannya benar. yaitu k dalam rentang [0, len (a) + len (b)]

Kasus dasar:

• Jika panjang salah satu array adalah 0, jawabannya adalah elemen ke-k dari array kedua.

Langkah-langkah pengurangan:

• Jika indeks tengah a+ indeks tengah bkurang darik
  • Jika elemen tengah alebih besar dari elemen tengah b, kita dapat mengabaikan paruh pertama b, sesuaikan k.
  • jika tidak, abaikan paruh pertama a, sesuaikan k.
• Lain jika kkurang dari jumlah indeks tengah adan b:
  • Jika elemen tengah alebih besar dari elemen tengah b, kita dapat mengabaikan paruh kedua dengan amana
  • kalau tidak, kita bisa mengabaikan paruh kedua b

Kode:

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)

Harap dicatat bahwa solusi saya adalah membuat salinan baru dari array yang lebih kecil di setiap panggilan, ini dapat dengan mudah dihilangkan dengan hanya melewatkan indeks awal dan akhir pada array asli.

Banyak orang menjawab pertanyaan "elemen terkecil ke-k dari dua larik terurut", tetapi biasanya hanya dengan ide-ide umum, bukan kode kerja yang jelas atau analisis kondisi batas.

Di sini saya ingin menguraikannya dengan hati-hati dengan cara saya pergi untuk membantu beberapa pemula untuk memahami, dengan kode Java saya yang berfungsi dengan benar. A1dan A2adalah dua array menaik yang diurutkan, dengan size1dan size2sebagai panjangnya masing-masing. Kita perlu mencari elemen terkecil ke-k dari gabungan kedua array tersebut. Di sini kami berasumsi bahwa (k > 0 && k <= size1 + size2), yang menyiratkan itu A1danA2 tidak boleh keduanya kosong.

Pertama, mari kita bahas pertanyaan ini dengan algoritma O (k) lambat. Caranya adalah dengan membandingkan elemen pertama dari kedua array, A1[0]dan A2[0]. Ambil yang lebih kecil, katakan A1[0]ke saku kita. Kemudian bandingkan A1[1]dengan A2[0], dan seterusnya. Ulangi tindakan ini sampai kantong kita mencapai kelemen. Sangat penting: Pada langkah pertama, kita hanya dapat berkomitmen A1[0]di saku kita. Kami TIDAK dapat menyertakan atau mengecualikanA2[0] !!!

Kode O (k) berikut memberi Anda satu elemen sebelum jawaban yang benar. Di sini saya menggunakannya untuk menunjukkan ide saya, dan menganalisis kondisi batas. Saya memiliki kode yang benar setelah yang ini:

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

Ide yang paling kuat adalah bahwa di setiap loop, kami selalu menggunakan pendekatan kasus dasar. Setelah berkomitmen ke elemen terkecil saat ini, kita selangkah lebih dekat ke target: elemen terkecil ke-k. Jangan pernah melompat ke tengah dan membuat diri Anda bingung dan tersesat!

Dengan mengamati base case kode di atas k == 1, k == size1+size2, dan menggabungkannya dengan itu A1danA2 keduanya tidak boleh kosong. Kita dapat mengubah logika menjadi gaya yang lebih ringkas di bawah ini.

Ini adalah kode yang berfungsi lambat tapi benar:

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

Sekarang kita dapat mencoba algoritma yang lebih cepat berjalan pada O (log k). Demikian pula, bandingkan A1[k/2]dengan A2[k/2]; jika A1[k/2]lebih kecil, maka semua elemen dari A1[0]sampai A1[k/2]harus ada di saku kita. Idenya adalah untuk tidak hanya berkomitmen pada satu elemen di setiap loop; langkah pertama mengandung k/2elemen. Sekali lagi, kami TIDAK dapat menyertakan atau mengecualikan A2[0]ke A2[k/2]. Jadi pada langkah pertama, kita tidak bisa lebih dari k/2elemen. Untuk langkah kedua, kita tidak bisa lebih dari k/4elemen ...

Setelah setiap langkah, kita semakin mendekati elemen k-th. Pada saat yang sama setiap langkah menjadi semakin kecil, sampai kita mencapai (step == 1), yaitu (k-1 == index1+index2). Kemudian kita bisa merujuk ke kasus dasar yang sederhana dan kuat lagi.

Berikut adalah kode yang berfungsi dengan benar:

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

Beberapa orang mungkin khawatir bagaimana jika (index1+index2)melompati k-1? Bisakah kita melewatkan kasus dasarnya(k-1 == index1+index2) ? Itu tidak mungkin. Anda dapat menambahkan 0,5 + 0,25 + 0,125 ..., dan Anda tidak akan pernah melampaui 1.

Tentu saja, sangat mudah untuk mengubah kode di atas menjadi algoritma rekursif:

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

Semoga analisis di atas dan kode Java dapat membantu Anda untuk memahami. Tapi jangan pernah menyalin kode saya sebagai pekerjaan rumah Anda! Bersulang ;)

Berikut adalah versi iteratif C ++ dari solusi @ lambdapilgrim (lihat penjelasan algoritme di sana):

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

Ia bekerja untuk semua 0 <= n < (size(a) + size(b))indeks dan memilikiO(log(size(a)) + log(size(b))) kompleksitas.

Contoh

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

Upaya saya untuk nomor k pertama, nomor k dalam 2 larik yang diurutkan, dan dalam n larik yang diurutkan:

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

Kode lengkap dengan utilitas debug dapat ditemukan di: https://github.com/brainclone/teasers/tree/master/kth

Inilah kode saya berdasarkan solusi 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;  
}  

Berikut adalah implementasi saya di C, Anda dapat merujuk ke penjelasan @Jules Olléon untuk algoritme: ide di balik algoritme adalah bahwa kita mempertahankan i + j = k, dan menemukan i dan j sehingga menjadi [i-1] <b [j-1] <a [i] (atau sebaliknya). Sekarang karena ada i elemen di 'a' lebih kecil dari b [j-1], dan elemen j-1 di 'b' lebih kecil dari b [j-1], b [j-1] adalah i + j-1 + 1 = elemen terkecil ke-k. Untuk menemukan i, j, algoritma melakukan pencarian dikotomis pada array.

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

Inilah solusi saya. Kode C ++ mencetak nilai terkecil ke-k serta jumlah iterasi untuk mendapatkan nilai terkecil ke-k dengan menggunakan loop yang menurut saya berada di urutan log (k). Namun kode tersebut membutuhkan k lebih kecil dari panjang array pertama yang merupakan batasan.

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

Kode pseudo pertama yang diberikan di atas, tidak berfungsi untuk banyak nilai. Misalnya, berikut adalah dua larik. int [] a = {1, 5, 6, 8, 9, 11, 15, 17, 19}; int [] b = {4, 7, 8, 13, 15, 18, 20, 24, 26};

Itu tidak berhasil untuk k = 3 dan k = 9 di dalamnya. Saya punya solusi lain. Itu diberikan di bawah ini.

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

}

Tapi ... itu juga tidak berfungsi untuk k = 5. Ada tangkapan genap / ganjil dari k yang tidak membiarkannya menjadi sederhana.

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

Berikut solusi tambang di java. Akan mencoba untuk lebih mengoptimalkannya

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

    }
}

Ini terinspirasi dari Algo di video youtube yang luar biasa

Tautan ke kode kompleksitas (log (n) + log (m))

Tautan ke Kode (log (n) * log (m))

Penerapan solusi (log (n) + log (m))

Saya ingin menambahkan penjelasan saya tentang masalah tersebut. Ini adalah masalah klasik di mana kita harus menggunakan fakta bahwa dua array diurutkan. kita telah diberikan dua array yang diurutkan arr1 dengan ukuran sz1 dan arr2 dengan ukuran sz2

a) Mari kita anggap jika

Memeriksa apakah k valid

k adalah> (sz1 + sz2)

maka kita tidak dapat menemukan elemen terkecil ke-k dalam gabungan kedua array yang diurutkan ryt Jadi kembalikan data yang tidak valid. b) Sekarang jika kondisi di atas bernilai salah dan kita memiliki nilai k yang valid dan layak,

Mengelola Kasus Edge

Kami akan menambahkan kedua array dengan nilai -tidak terhingga di depan dan + nilai tak terhingga di ujung untuk mencakup kasus tepi k = 1,2 dan k = (sz1 + sz2-1), (sz1 + sz2) dll.

Sekarang kedua array memiliki ukuran (sz1 + 2) dan (sz2 + 2) masing-masing

Algoritma Utama

Sekarang, kita akan melakukan pencarian biner di arr1. Kita akan melakukan pencarian biner di arr1 mencari indeks i, startIndex <= i <= endIndex

sehingga jika kita menemukan indeks j yang sesuai di arr2 menggunakan kendala {(i + j) = k}, maka if

if (arr2 [j-1] <arr1 [i] <arr2 [j]) , maka arr1 [i] adalah terkecil ke-k (Kasus 1)

else if (arr1 [i-1] <arr2 [j] <arr1 [i]) , maka arr2 [i] adalah terkecil ke-k (Kasus 2)

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

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

Karena kita tahu bahwa elemen terkecil ke-k memiliki (k-1) elemen yang lebih kecil darinya dalam penyatuan kedua array ryt? Begitu,

Dalam Kasus1 , apa yang kami lakukan, kami memastikan bahwa ada total (k-1) elemen yang lebih kecil ke arr1 [i] karena elemen yang lebih kecil dari arr1 [i] dalam array arr1 adalah i-1 jumlahnya dari yang kami ketahui (arr2 [ j-1] <arr1 [i] <arr2 [j]) dan jumlah elemen yang lebih kecil dari arr1 [i] di arr2 adalah j-1 karena j ditemukan menggunakan (i-1) + (j-1) = (k -1) Jadi elemen terkecil ke-k adalah arr1 [i]

Tetapi jawabannya mungkin tidak selalu datang dari array pertama yaitu arr1 jadi kami memeriksa case2 yang juga memenuhi sama seperti case 1 karena (i-1) + (j-1) = (k-1). Sekarang jika kita memiliki (arr1 [i-1] <arr2 [j] <arr1 [i]) kita memiliki total elemen k-1 yang lebih kecil dari arr2 [j] dalam penyatuan kedua array jadi itu elemen terkecil ke-k.

Dalam case3 , untuk membentuknya menjadi case 1 atau case 2, kita perlu menambahkan i dan j akan ditemukan sesuai dengan batasan {(i + j) = k} yaitu dalam pencarian biner pindah ke bagian kanan yaitu buat startIndex = middleIndex

Dalam case4 , untuk membentuknya menjadi case 1 atau case 2, kita perlu menurunkan i dan j akan ditemukan sesuai dengan batasan {(i + j) = k} yaitu dalam pencarian biner pindah ke bagian kiri yaitu make endIndex = middleIndex .

Sekarang bagaimana menentukan startIndex dan endIndex pada awal pencarian biner melalui arr1 dengan startindex = 1 dan endIndex = ??. Kita perlu memutuskan.

Jika k> sz1, endIndex = (sz1 + 1), lain endIndex = k;

Karena jika k lebih besar dari ukuran array pertama, kita mungkin harus melakukan pencarian biner di seluruh array arr1, jika tidak kita hanya perlu mengambil k elemen pertama karena elemen sz1-k tidak pernah bisa berkontribusi dalam menghitung k terkecil.

KODE Di Bawah Ini

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

}

Untuk Solusi kompleksitas (log (n) * log (m))

Hanya saya melewatkan keuntungan dari fakta bahwa untuk setiap i j dapat ditemukan menggunakan kendala {(i-1) + (j-1) = (k-1)} Jadi untuk setiap ii selanjutnya menerapkan pencarian biner pada array kedua untuk menemukan j sehingga arr2 [j] <= arr1 [i]. Jadi solusi ini dapat dioptimalkan lebih lanjut

Pada dasarnya, melalui pendekatan ini Anda dapat membuang k / 2 elemen di setiap langkah. K akan berubah secara rekursif dari k => k / 2 => k / 4 => ... hingga mencapai 1. Jadi, Kompleksitas Waktu adalah O (logk)

Pada k = 1, kita mendapatkan yang terendah dari dua larik.

Kode berikut ada di JAWA. Harap dicatat bahwa kami mengurangi 1 (-1) dalam kode dari indeks karena indeks larik Java dimulai dari 0 dan bukan 1, misalnya. k = 3 diwakili oleh elemen dalam indeks ke-2 dari sebuah array.

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

Kompleksitas Waktu adalah O (log (min (n, m)))

Sebagian besar jawaban yang saya temukan di sini berfokus pada kedua larik. meskipun bagus tetapi lebih sulit untuk diterapkan karena ada banyak kasus tepi yang perlu kita tangani. Selain itu sebagian besar implementasinya bersifat rekursif yang menambah kompleksitas ruang stack rekursi. Jadi, alih-alih berfokus pada kedua larik, saya memutuskan untuk hanya fokus pada larik yang lebih kecil dan melakukan pencarian biner hanya pada larik yang lebih kecil dan menyesuaikan penunjuk untuk larik kedua berdasarkan nilai penunjuk di Array pertama. Dengan implementasi berikut, kita mendapatkan kompleksitas O(log(min(n,m))dengan O(1)kompleksitas ruang.

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

Kami memiliki rentang [low, high]untuk larik adan kami mempersempit rentang ini saat kami melangkah lebih jauh melalui algoritme. sizeAmenunjukkan berapa banyak item dari kitem berasal dari array adan itu berasal dari nilai lowdan high. sizeBadalah definisi yang sama kecuali kita menghitung nilai sedemikian rupasizeA+sizeB=k . Berdasarkan nilai-nilai pada kedua batas tersebut dengan kesimpulan bahwa kita harus memperluas ke sisi kanan dalam larik aatau menyusut ke sisi kiri. jika kita terjebak di posisi yang sama itu berarti kita menemukan solusi dan kita akan mengembalikan nilai maksimal di posisi sizeA-1dari adan sizeB-1dari b.

Periksa kode ini.

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

Di bawah kode C # untuk Menemukan Elemen Terkecil ke-k dalam Gabungan Dua Array yang Diurutkan. Kompleksitas Waktu: 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);

            }
        }