Как найти k-й наименьший элемент в объединении двух отсортированных массивов?

107

Это вопрос домашнего задания. Они говорят, что принимает O(logN + logM)где Nи Mявляются длинами массивов.

Назовем массивы aи b. Очевидно, мы можем игнорировать все a[i]и b[i]где i> k.
Сначала сравним a[k/2]и b[k/2]. Пусть b[k/2]> a[k/2]. Поэтому мы можем отбросить и все b[i], где i> k / 2.

Теперь у нас есть все a[i], где i <k, и все b[i], где i <k / 2, чтобы найти ответ.

Каким будет следующий шаг?

Майкл
источник
6
Были ли все эти шаги включены в задание, или они являются началом вашего алгоритма?
Кендрик
19
Шаги выше мои.
Майкл
Имеется в O(logN + logM)виду только время, необходимое для поиска k-го элемента? Можно ли выполнить предварительную обработку объединения заранее?
Дэвид Вайзер
1
@ Дэвид. Никакой предварительной обработки не ожидается.
Майкл
3
Допускаются ли дубликаты в массивах?
Дэвид Вайзер

Ответы:

49

Вы получили это, просто продолжайте! И будьте осторожны с индексами ...

Чтобы немного упростить, я предполагаю, что N и M> k, поэтому сложность здесь O (log k), что составляет O (log N + log M).

Псевдокод:

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]

Для демонстрации вы можете использовать инвариант цикла i + j = k, но я не буду выполнять всю вашу домашнюю работу :)

Жюль Оллеон
источник
14
Это не настоящее доказательство, но идея алгоритма состоит в том, что мы поддерживаем i + j = k и находим такие i и j так, чтобы a [i-1] <b [j-1] <a [i] ( или наоборот). Теперь, поскольку в 'a' i элементов меньше, чем b [j-1], и j-1 элементов в 'b' меньше, чем b [j-1], b [j-1] является i + j-1 + 1 = k-й наименьший элемент. Чтобы найти такие i, j, алгоритм выполняет дихотомический поиск по массивам. Имеет смысл?
Жюль Оллеон
8
Почему O (log k) равно O (log n + log m)?
Раджендра Уппал
7
Это не работает, если все значения в массиве 1 предшествуют значениям в массиве 2.
Джон Курлак,
3
Почему вы сначала использовали k / 4 как ступеньку?
Мэгги
2
Как заметил @JohnKurlak, это не работает для значений, где целое a меньше, чем b, см. Repl.it/HMYf/0
Джереми С.
70

Надеюсь, я не отвечаю на вашу домашнюю работу, так как этот вопрос был задан больше года назад. Вот хвостовое рекурсивное решение, которое займет время log (len (a) + len (b)).

Предположение: исходные данные верны. т.е. k находится в диапазоне [0, len (a) + len (b)]

Базовые случаи:

  • Если длина одного из массивов равна 0, ответ - k-й элемент второго массива.

Шаги восстановления:

  • Если средний индекс a+ средний индекс bменьше чемk
    • Если средний элемент aбольше, чем средний элемент b, мы можем игнорировать первую половину b, отрегулируйте k.
    • иначе игнорируйте первую половину a, настройте k.
  • Иначе, если kменьше суммы средних индексов aи b:
    • Если средний элемент aбольше, чем средний элемент b, мы можем смело игнорировать вторую половинуa
    • иначе мы можем игнорировать вторую половину b

Код:

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)

Обратите внимание, что мое решение создает новые копии меньших массивов при каждом вызове, это можно легко устранить, передав только начальные и конечные индексы в исходных массивах.

лямбдапилгрим
источник
4
почему вы называете его, kthlargest()он возвращает (k+1)-й наименьший элемент, например, 1это второй наименьший элемент, 0,1,2,3т.е. ваша функция возвращает sorted(a+b)[k].
jfs
2
Я преобразовал ваш код в C ++ . Вроде работает
jfs
1
не могли бы вы объяснить, почему так важно сравнивать сумму средних индексов a и b с k?
Мэгги
3
На этапах сокращения важно избавиться от количества элементов в одном из массивов, пропорциональных его длине, чтобы сделать время выполнения логарифмическим. (Здесь мы избавляемся от половины). Для этого нам нужно выбрать один массив, одну из половин которого мы можем игнорировать. Как мы это делаем? Уверенно исключив половину, мы точно знаем, что в ней не будет k-го элемента.
lambdapilgrim
1
Сравнение k с суммой полудлин массивов дает нам информацию о том, какую половину одного из массивов можно исключить. Если k больше суммы полудлин, мы знаем, что первая половина одного из массивов может быть удалена. Напротив, если k меньше. Обратите внимание, что мы не можем удалить половину из каждого массива сразу. Чтобы решить, какую половину какого массива удалить, мы используем тот факт, что оба массива отсортированы, поэтому, если k больше суммы полудлин, мы можем исключить первую половину массива, средний элемент которой меньше два средних элемента. Наоборот.
lambdapilgrim
35

Многие люди ответили на вопрос «k-й наименьший элемент из двух отсортированных массивов», но обычно с помощью только общих идей, а не четкого рабочего кода или анализа граничных условий.

Здесь я хотел бы подробно рассказать о том, как я пошел, чтобы помочь некоторым новичкам понять, с моим правильным рабочим кодом Java. A1и A2- два отсортированных по возрастанию массива с длиной size1и size2длиной соответственно. Нам нужно найти k-й наименьший элемент из объединения этих двух массивов. Здесь мы разумно предполагаем (k > 0 && k <= size1 + size2), что подразумевает это A1и A2не может быть одновременно пустым.

Во-первых, давайте подойдем к этому вопросу с помощью медленного алгоритма O (k). Метод заключается в сравнении первого элемента как массива, так A1[0]и A2[0]. Меньшую возьмите, скажем A1[0], в карман. Потом сравните A1[1]с A2[0]и так далее. Повторяйте это действие, пока наш карман не достигнет kэлементов. Очень важно: на первом этапе мы можем взять на себя обязательства только A1[0]в нашем кармане. Мы НЕ можем включать или исключать A2[0]!!!

Следующий код O (k) дает вам один элемент перед правильным ответом. Здесь я использую его, чтобы показать свою идею и анализ граничных условий. После этого у меня правильный код:

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

Самая сильная идея заключается в том, что в каждом цикле мы всегда используем подход базового случая. После привязки к текущему наименьшему элементу мы приближаемся на один шаг к цели: k-му наименьшему элементу. Никогда не прыгайте в середину и не запутайтесь и не потеряйтесь!

Наблюдая выше код базового варианта k == 1, k == size1+size2, и в сочетании с , что A1и A2оба не могут быть пустыми. Мы можем превратить логику в более лаконичный стиль ниже.

Вот медленный, но правильный рабочий код:

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

Теперь мы можем попробовать более быстрый алгоритм, работающий на O (log k). Точно так же сравните A1[k/2]с A2[k/2]; если A1[k/2]меньше, то все элементы от A1[0]до A1[k/2]должны быть у нас в кармане. Идея состоит в том, чтобы не просто фиксировать один элемент в каждом цикле; первый шаг содержит k/2элементы. Опять же, мы НЕ можем A2[0]в A2[k/2]любом случае включать или исключать . Итак, на первом этапе мы не можем идти дальше k/2элементов. Для второго шага мы не можем идти дальше k/4элементов ...

После каждого шага мы приближаемся к k-му элементу. В то же время каждый шаг становится все меньше и меньше, пока мы не дойдем до того (step == 1), что есть (k-1 == index1+index2). Затем мы снова можем обратиться к простому и мощному базовому случаю.

Вот рабочий правильный код:

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

Некоторые могут волноваться, а вдруг (index1+index2)перепрыгнет к-1? Можем ли мы пропустить базовый вариант (k-1 == index1+index2)? Это невозможно. Вы можете сложить 0,5 + 0,25 + 0,125 ... и никогда не выйдете за пределы 1.

Конечно, приведенный выше код очень легко превратить в рекурсивный алгоритм:

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

Надеюсь, что приведенный выше анализ и код Java помогут вам понять. Но никогда не копируйте мой код в качестве домашнего задания! Ура;)

Фэй
источник
1
Большое спасибо за ваши прекрасные объяснения и ответ, +1 :)
Хенгаме
В первом коде не должно быть else if (A1[size1 - 1].compareTo(A2[size2 - 1]) < 0) вместо else if (A1[size1 - 1].compareTo(A2[size2 - 1]) > 0)? (В коде kthSmallestSlowWithFault)
Хенгаме 01
Спасибо @Fei. Отличное объяснение. Поразительно, сколько неверных ответов на эту проблему ходит в Интернете. Еще более удивительно то, что принятый ей ответ на SO по этому вопросу всегда неверен. Кажется, никто не хочет проверять ответы.
Captain Fogetti
Возможно, отключение решения O (k) после некоторых шагов (сказано 15), поскольку диапазон шагов уменьшается довольно быстро.
Sky
1
Ни в одном из рекурсивных вызовов размеры A1 или A2 не уменьшаются.
Адитья Джоши
5

Вот итеративная версия решения @lambdapilgrim на C ++ (см. Объяснение алгоритма там):

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

Он работает для всех 0 <= n < (size(a) + size(b))индексов и имеет O(log(size(a)) + log(size(b)))сложность.

пример

#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;
}
jfs
источник
4

Моя попытка для первых k чисел, k-го числа в 2 отсортированных массивах и в n отсортированных массивах:

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

Полный код с утилитами отладки можно найти по адресу: https://github.com/brainclone/teasers/tree/master/kth

Цичао Донг
источник
3

Вот мой код, основанный на решении Жюля Оллеона:

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;  
}  
превосходно
источник
1
В некоторых случаях это не сработает. Например, int a2 [] = {1,2,3,4, 5}; int a1 [] = {5,6,8,10,12}; getNth (a1, a2, 7). Индекс массива выйдет за границы.
Джей
2

Вот моя реализация на C, вы можете обратиться к объяснениям алгоритма @Jules Olléon: идея алгоритма заключается в том, что мы поддерживаем i + j = k и находим такие i и j, чтобы a [i-1] <b [j-1] <a [i] (или наоборот). Теперь, поскольку в 'a' i элементов меньше, чем b [j-1], и j-1 элементов в 'b' меньше, чем b [j-1], b [j-1] является i + j-1 + 1 = k-й наименьший элемент. Чтобы найти такие i, j, алгоритм выполняет дихотомический поиск по массивам.

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);
   }
 }
неплохо
источник
2

Вот мое решение. Код C ++ печатает k-е наименьшее значение, а также количество итераций для получения k-го наименьшего значения с помощью цикла, который, на мой взгляд, находится в порядке log (k). Однако код требует, чтобы k было меньше, чем длина первого массива, что является ограничением.

#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;
    }
}
Картикеян Св
источник
1

Первый псевдокод, представленный выше, не работает для многих значений. Например, вот два массива. int [] a = {1, 5, 6, 8, 9, 11, 15, 17, 19}; int [] b = {4, 7, 8, 13, 15, 18, 20, 24, 26};

В нем не работало при k = 3 и k = 9. У меня есть другое решение. Он приводится ниже.

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

}

Но ... он также не работает для k = 5. Есть четный / нечетный улов k, который не позволяет ему быть простым.

sn.anurag
источник
1
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]);
        }
    }
}
Хришикеш Мишра
источник
1

Вот мое решение на java. Постараюсь еще больше оптимизировать

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

    }
}

Это вдохновлено Algo в замечательном видео на YouTube.

M Sach
источник
1

Ссылка на сложность кода (log (n) + log (m))

Ссылка на код (log (n) * log (m))

Реализация решения (log (n) + log (m))

Я хотел бы добавить свое объяснение к проблеме. Это классическая проблема, когда мы должны использовать тот факт, что два массива отсортированы. нам даны два отсортированных массива arr1 размера sz1 и arr2 размера sz2

а) Предположим, если

Проверка правильности k

k> (sz1 + sz2)

тогда мы не можем найти k-й наименьший элемент в объединении обоих отсортированных массивов ryt Итак, верните неверные данные. б) Теперь, если вышеупомянутое условие выполнено false и у нас есть действительное и допустимое значение k,

Управление крайними случаями

Мы добавим оба массива значениями -infinity спереди и значениями + infinity в конце, чтобы охватить крайние случаи k = 1,2 и k = (sz1 + sz2-1), (sz1 + sz2) и т. Д.

Теперь оба массива имеют размер (sz1 + 2) и (sz2 + 2) соответственно.

Основной алгоритм

Теперь мы выполним двоичный поиск по arr1. Мы выполним двоичный поиск по arr1 в поисках индекса i, startIndex <= i <= endIndex

такой, что если мы найдем соответствующий индекс j в arr2, используя ограничение {(i + j) = k}, то если

если (arr2 [j-1] <arr1 [i] <arr2 [j]) , то arr1 [i] является k-м наименьшим (случай 1)

иначе, если (arr1 [i-1] <arr2 [j] <arr1 [i]) , то arr2 [i] является k-м наименьшим (случай 2)

else означает либо arr1 [i] <arr2 [j-1] <arr2 [j] (Case3)

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

Поскольку мы знаем, что k-й наименьший элемент имеет (k-1) элементов меньше, чем он в объединении обоих массивов ryt? Так,

В случае 1 , что мы сделали, мы обеспечили наличие в общей сложности (k-1) меньших элементов для arr1 [i], потому что элементы меньше, чем arr1 [i] в ​​массиве arr1, имеют количество i-1, чем мы знаем (arr2 [ j-1] <arr1 [i] <arr2 [j]), а количество элементов меньше arr1 [i] в ​​arr2 равно j-1, поскольку j находится с использованием (i-1) + (j-1) = (k -1) Таким образом, k-й наименьший элемент будет arr1 [i]

Но ответ может не всегда поступать из первого массива, то есть arr1, поэтому мы проверили case2, который также удовлетворяет аналогично случаю 1, потому что (i-1) + (j-1) = (k-1). Теперь, если у нас есть (arr1 [i-1] <arr2 [j] <arr1 [i]), у нас есть всего k-1 элементов, меньших, чем arr2 [j] в объединении обоих массивов, так что это k-й наименьший элемент.

В случае 3 , чтобы преобразовать его в любой из случаев 1 или 2, нам нужно увеличить i, и j будет найдено в соответствии с использованием ограничения {(i + j) = k}, т.е. при двоичном поиске перейти в правую часть, т.е. сделать startIndex = middleIndex

В случае 4 , чтобы преобразовать его в любой из случаев 1 или 2, нам нужно уменьшить i, и j будет найден в соответствии с использованием ограничения {(i + j) = k}, т.е. при двоичном поиске перейти в левую часть, т.е. сделать endIndex = middleIndex .

Теперь, как определить startIndex и endIndex в начале двоичного поиска по arr1 с startindex = 1 и endIndex = ??. Нам нужно решить.

Если k> sz1, endIndex = (sz1 + 1), иначе endIndex = k;

Поскольку, если k больше, чем размер первого массива, нам может потребоваться выполнить двоичный поиск по всему массиву arr1, иначе нам нужно взять только первые k его элементов, потому что элементы sz1-k никогда не могут участвовать в вычислении k-го наименьшего.

КОД показан ниже

// Complexity    O(log(n)+log(m))

#include<bits/stdc++.h>
using namespace std;
#define f(i,x,y) for(int i = (x);i < (y);++i)
#define F(i,x,y) for(int i = (x);i > (y);--i)
int max(int a,int b){return (a > b?a:b);}
int min(int a,int b){return (a < b?a:b);}
int mod(int a){return (a > 0?a:((-1)*(a)));}
#define INF 1000000




int func(int *arr1,int *arr2,int sz1,int sz2,int k)

{

if((k <= (sz1+sz2))&&(k > 0))

{
int s = 1,e,i,j;
if(k > sz1)e = sz1+1;
else e = k;
while((e-s)>1)
{
  i = (e+s)/2;
  j = ((k-1)-(i-1)); 
  j++;
  if(j > (sz2+1)){s = i;}
  else if((arr1[i] >= arr2[j-1])&&(arr1[i] <= arr2[j]))return arr1[i];
  else if((arr2[j] >= arr1[i-1])&&(arr2[j] <= arr1[i]))return arr2[j];
  else if(arr1[i] < arr2[j-1]){s = i;}
  else if(arr1[i] > arr2[j]){e = i;}
  else {;}
}
i = e,j = ((k-1)-(i-1));j++;
if((arr1[i] >= arr2[j-1])&&(arr1[i] <= arr2[j]))return arr1[i];
else if((arr2[j] >= arr1[i-1])&&(arr2[j] <= arr1[i]))return arr2[j];
else
{
  i = s,j = ((k-1)-(i-1));j++;
  if((arr1[i] >= arr2[j-1])&&(arr1[i] <= arr2[j]))return arr1[i];
  else return arr2[j];
}

  }

 else

{
cout << "Data Invalid" << endl;
return -INF;

}

}





int main()

{
int n,m,k;
cin >> n >> m >> k;
int arr1[n+2];
int arr2[m+2];
f(i,1,n+1)
cin >> arr1[i];
f(i,1,m+1)
cin >> arr2[i];
arr1[0] = -INF;
arr2[0] = -INF;
  arr1[n+1] = +INF;  
arr2[m+1] = +INF; 
int val = func(arr1,arr2,n,m,k);
if(val != -INF)cout << val << endl;   
return 0;

}

Для решения сложности (log (n) * log (m))

Просто я упустил преимущество того факта, что для каждого i j можно найти с помощью ограничения {(i-1) + (j-1) = (k-1)} Таким образом, для каждого ii дополнительно применялся двоичный поиск по второму массиву найти j такое, что arr2 [j] <= arr1 [i]. Таким образом, это решение может быть дополнительно оптимизировано

Винаяк Сангар
источник
1

По сути, с помощью этого подхода вы можете отбрасывать k / 2 элементов на каждом шаге. K будет рекурсивно изменяться от k => k / 2 => k / 4 => ... до тех пор, пока не достигнет 1. Таким образом, сложность времени равна O (logk)

При k = 1 мы получаем самый низкий из двух массивов.

Следующий код находится на JAVA. Обратите внимание, что мы вычитаем 1 (-1) в коде из индексов, потому что индекс массива Java начинается с 0, а не с 1, например. k = 3 представлен элементом во 2-м индексе массива.

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));
    }
}
ФаадуБаалак
источник
1
#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;
}

Время Complexcity равно O (log (min (n, m)))

Голова и хвост
источник
1

Большинство ответов, которые я нашел здесь, касаются обоих массивов. Хотя это хорошо, но его сложнее реализовать, так как есть много крайних случаев, о которых нам нужно позаботиться. Кроме того, большинство реализаций являются рекурсивными, что увеличивает пространственную сложность стека рекурсии. Поэтому вместо того, чтобы сосредотачиваться на обоих массивах, я решил просто сосредоточиться на меньшем массиве и выполнить двоичный поиск только на меньшем массиве и настроить указатель для второго массива на основе значения указателя в первом массиве. В следующей реализации мы получаем сложность O(log(min(n,m))с O(1)пространственной сложностью.

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

У нас есть диапазон [low, high]для массива, aи мы сужаем его по мере прохождения алгоритма. sizeAпоказывает, сколько элементов из kэлементов находится в массиве, aи является производным от значения lowи high. sizeBто же определение, за исключением того, что мы вычисляем значение таким образом, чтобы sizeA+sizeB=k. На основе значений на этих двух границах делается вывод, что мы должны расширить до правой стороны в массиве aили сжать до левой стороны. если мы застряли в той же позиции, это означает, что мы нашли решение и вернем максимальное количество значений в позиции sizeA-1from aи sizeB-1from b.

Арнольд
источник
0

Проверьте этот код.

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();
Ананта Кришнан
источник
Предоставьте объяснение
Абхиджит Саркар
0

Ниже кода C # для поиска k-го наименьшего элемента в объединении двух отсортированных массивов. Сложность времени: 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);

            }
        }
Пиюш Патель
источник
ошибки нет, я проверил свой код перед тем, как опубликовать в SO
Пиюш Патель
1
Спасибо sammy333, обновил код. теперь рабочий
Пиюш Патель
(Не вычислить midAиз endAесли k < nПроверить коротких массивов, начиная с. return B[startB + k - 1];.)
глиняный кувшин