Как найти k-й наименьший элемент в объединении двух отсортированных массивов?
Это вопрос домашней работы. Говорят, что требуется 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], где я < k и всех b[i], где я < k/2, чтобы найти ответ.
Каков следующий шаг?
Ответы
Ответ 1
У вас это есть, просто продолжайте! И будьте осторожны с индексами...
Чтобы упростить бит, я предполагаю, что 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]
Для демонстрации вы можете использовать инвариант цикла я + j = k, но я не буду выполнять все домашние задания:)
Ответ 2
Надеюсь, я не отвечу на вашу домашнюю работу, поскольку прошло уже больше года с тех пор, как был задан этот вопрос. Вот хвостовое рекурсивное решение, которое будет принимать время 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)
Обратите внимание, что мое решение создает новые копии меньших массивов в каждом вызове, это можно легко устранить, только передавая начальные и конечные индексы на исходных массивах.
Ответ 3
Многие люди ответили на этот вопрос "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-й наименьший элемент. Никогда не прыгайте в середину и не смущайтесь и не теряйтесь!
Соблюдая приведенный выше код base case 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) перепрыгнуть через k-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 помогут вам понять. Но никогда не копируйте мой код в качестве домашней работы! Приветствия;)
Ответ 4
Здесь итеративная версия С++ @lambdapilgrim solution (см. объяснение алгоритма):
#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;
}
Ответ 5
Моя попытка для первых 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
Ответ 6
Здесь мой код основан на решении Жюля Оллеона:
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;
}
Ответ 7
Вот моя реализация в C, вы можете ссылаться на @Jules Olléon, объясняющую алгоритм: идея алгоритма заключается в том, что мы поддерживаем я + j = k и находим такие я и j, чтобы a [i-1 ] < b [j-1] a [i] (или наоборот). Теперь, поскольку в 'a' есть элементы i, меньшие, чем b [j-1], а j-1 элементов в 'b' меньше b [j-1], b [j-1] является я + 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);
}
}
Ответ 8
Вот мое решение. Код С++ печатает 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;
}
}
Ответ 9
Проверьте этот код.
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();
Ответ 10
Первый псевдо-код, приведенный выше, не работает для многих значений. Например,
вот два массива.
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, который не позволяет ему быть простым.
Ответ 11
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]);
}
}
}
Ответ 12
Вот мое решение в 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
Ответ 13
Ссылка на код сложность (log (n) + log (m))
Ссылка на код (log (n) * log (m))
Реализация решения (log (n) + log (m))
Я хотел бы добавить свое объяснение к проблеме.
Это классическая проблема, когда мы должны использовать тот факт, что два массива отсортированы.
нам были предоставлены два отсортированных массива arr1 размера sz1 и arr2 размера sz2
a) Предположим, что если
Проверка Если k действителен
k is > (sz1 + sz2)
то мы не сможем найти k-й наименьший элемент в объединении обоих отсортированных массивов ryt So return Недействительные данные.
б) Теперь, если приведенное выше условие имеет значение false, и мы имеем действительное и допустимое значение k,
Управление пограничными шкафами
Мы добавим оба массива значения -infinity в начале и + бесконечности в конце, чтобы покрыть краевые случаи k = 1,2 и k = (sz1 + sz2-1), (sz1 + sz2) и т.д.
Теперь оба массива имеют размер (sz1 + 2) и (sz2 + 2) соответственно
Главный алгоритм
Теперь мы будем выполнять двоичный поиск по arr1. Мы будем выполнять двоичный поиск в arr1, ищем индекс i, startIndex <= я <= endIndex
такое, что если мы найдем соответствующий индекс j в arr2, используя ограничение {(i + j) = k}, то если
если (arr2 [j-1] < arr1 [i] < arr2 [j]), то arr1 [i] является k-м наименьшим (случай 1)
else if (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)
Так как мы знаем, что kth наименьший элемент имеет (k-1) элементы, меньшие, чем он в объединении массивов ryt? Таким образом,
В Case1, что мы сделали, мы гарантировали, что в arr1 [i] есть сумма (k-1) меньших элементов, потому что элементы, меньшие, чем arr1 [i] в массиве arr1, равны я -1 в количестве, чем мы знаем (arr2 [j-1] < arr1 [i] < arr2 [j]), а число элементов, меньшее, чем arr1 [i] в arr2, равно j-1, поскольку j найдено с использованием (i -1) + (j-1) = (k-1) Таким образом, k-й наименьший элемент будет arr1 [i]
Но ответ не всегда получается из первого массива ie arr1, поэтому мы проверили case2, который также удовлетворяет аналогично случаю 1, потому что (i-1) + (j-1) = (k- 1). Теперь, если мы имеем (arr1 [i-1] < arr2 [j] < arr1 [i]), мы имеем общее число k-1, меньшее, чем arr2 [j], в объединении обоих массивов, поэтому его k-е наименьшее элемент.
В case3, чтобы сформировать его в любом случае 1 или в случае 2, нам нужно увеличить i, а j будет найдено в соответствии с ограничением {(i + j) = k}, то есть в двоичном поиск перемещается в правую часть, т.е. make startIndex = middleIndex
В case4, чтобы сформировать его в любом случае 1 или в случае 2, нам нужно уменьшить i, а j будет найдено в соответствии с ограничением {(i + j) = k}, то есть в двоичном поиск перемещается в левую часть, т.е. make endIndex = middleIndex.
Теперь, как решить startIndex и endIndex в начале двоичного поиска по arr1
с startindex = 1 и endIndex =??. Нам нужно решить.
Если k > sz1, endIndex = (sz1 + 1), else 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))
Просто я пропустил, используя преимущество того, что для каждого я j можно найти с помощью ограничения {(i-1) + (j-1) = (k-1)} Итак, для каждого ii дальнейшее применение бинарного поиска на втором массиве, чтобы найти j таким образом, что arr2 [j] <= arr1 [i]. Это решение можно оптимизировать далее
Ответ 14
В принципе, с помощью этого подхода вы можете отбросить k/2 элемента на каждом шаге.
K будет рекурсивно изменяться от k = > k/2 = > k/4 = > ... до достижения 1.
Итак, сложность времени O (logk)
При k = 1 мы получаем самый низкий из двух массивов.
Следующий код находится в JAVA. Обратите внимание, что мы вычитаем 1 (-1) в коде из индексов, потому что индекс массива Java начинается с 0, а не 1, например. k = 3 представляется элементом во втором индексе массива.
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));
}
}
Ответ 15
Ниже код С# для поиска 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);
}
}
