How to find the kth largest element in the union of two sorted arrays?
algorithm, c++, language-agnostic
Solution
From your comments I understand that you want to find k-th smallest value given 2 inversely sorted array e.g., for `a={5,4,3}, b={2,1,0};` and `k=1` the expected result is `0` i.e., the minimum value -- the first smallest value (it means that `k` is counted from `1`).
Given `nsmallest()` function that works on sorted arrays and accepts a custom comparator you could:
#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(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;
}
I've used @Neil's suggestion to fix the index and @lambdapilgrim's answer for the algorithm:
#include <cassert>
#include <iterator>
template<class RandomIterator, class Compare>
typename std::iterator_traits<RandomIterator>::value_type
nsmallest(RandomIterator firsta, RandomIterator lasta,
RandomIterator firstb, RandomIterator lastb,
size_t n,
Compare less) {
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)
return less(*(firstb + midb), *(firsta + mida)) ?
nsmallest(firsta, lasta, firstb + midb + 1, lastb, n - (midb + 1), less) :
nsmallest(firsta + mida + 1, lasta, firstb, lastb, n - (mida + 1), less);
else
return less(*(firstb + midb), *(firsta + mida)) ?
nsmallest(firsta, firsta + mida, firstb, lastb, n, less) :
nsmallest(firsta, lasta, firstb, firstb + midb, n, less);
}
Problem
I need to find the `k` largest element in two sorted arrays, but with a twist. This algorithm assumes `k<=max(m,n)` and indexes go awry when `k>max(m,n)`. In my problem i know that will always be `k>(m+n)/2` and hence `k>min(m,n)` so i need to change Jules Olléon's answer a little bit...i just don't see which bit :~ I've found this link page 3, but there is bug there (when implemented, it doesn't return the right answer) I know a quick fix would be to multiply both arrays by -1 and take the k smallest of that union and multiply back the answer by -1 but that'll make the code unreadable. This is not a homework. Ok, i think i'm missunderstanding Neil's answer or something else because this is what i give 'him' ``` #include <algorithm> #include <fstream> #include <iostream> #include <stdio.h> #include <stdlib.h> #include <time.h> #include <vector> #include <Eigen/Dense> using namespace Eigen; using Eigen::VectorXf; using Eigen::VectorXi; float getNth(VectorXf& v1,VectorXf& v2,int& n){ int step=(n/4),i1=(n/2),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 p,q,n,k,l; float sol; std:: cout << "enter p " << std::endl; std::cin >> p; std:: cout << "enter q " << std::endl; std::cin >> q; n=p+q; std:: cout << " enter k larger than " << std::min(p,q) << " and smaller than " << n-1 << std::endl; std::cin >> k; k=n-k-1; srand(time(NULL)); VectorXf v1=VectorXf::Random(p); srand(time(NULL)); VectorXf v2=VectorXf::Random(q); VectorXf v3(n); v3 << v1, v2; std::sort(v3.data(),v3.data()+v3.size(),std::greater<float>()); //std::greater<float>() std::sort(v1.data(),v1.data()+v1.size(),std::greater<float>()); std::sort(v2.data(),v2.data()+v2.size(),std::greater<float>()); sol=getNth(v1,v2,k); std::cout << sol << std::endl; std::cout << v3(k) << std::endl; return 0; } ``` and this is what i get: ``` enter p 12 enter q 32 enter k larger than 12 and smaller than 43 13 nthoftwo: /Desktop/work/p1/geqw4/vi3/out/sp/ccode/eigen/Eigen/src/Core/DenseCoeffsBase.h:409: Eigen::DenseCoeffsBase<Derived, 1>::Scalar& Eigen::DenseCoeffsBase<Derived, 1>::operator()(Eigen::DenseCoeffsBase<Derived, 1>::Index) [with Derived = Eigen::Matrix<float, -0x00000000000000001, 1>, Eigen::DenseCoeffsBase<Derived, 1>::Scalar = float, Eigen::DenseCoeffsBase<Derived, 1>::Index = long int]: Assertion `index >= 0 && index < size()' failed. Aborted (core dumped) ``` if you are unfamiliar with eigen: the error is an index out of bound error caused by `getNth(v1,v2,k)` EDIT: this is a very minor modification on J.F. Sebastian' simple and elegant solution below --all mistakes are mine, but it seems to work. The aim was to work with the original indexes (i.e. i'm not sure Neil's idea is indispensable). ``` #include <algorithm> #include <fstream> #include <iostream> #include <stdio.h> #include <stdlib.h> #include <time.h> #include <vector> #include <cassert> #include <iterator> #include <Eigen/Dense> using namespace Eigen; using Eigen::VectorXf; using Eigen::VectorXi; template<class RandomIterator,class Compare> typename std::iterator_traits<RandomIterator>::value_type nsmallest(RandomIterator firsta,RandomIterator lasta,RandomIterator firstb,RandomIterator lastb,size_t n,Compare less) { 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) return less(*(firstb+midb),*(firsta+mida))? nsmallest(firsta,lasta,firstb+midb+1,lastb,n-(midb+1),less): nsmallest(firsta+mida+1,lasta,firstb,lastb,n-(mida+1),less); else return less(*(firstb+midb),*(firsta+mida))? nsmallest(firsta,firsta+mida,firstb,lastb,n,less): nsmallest(firsta,lasta,firstb,firstb+midb,n,less); } int main(){ int p,q,n,k,l; float sol; std:: cout << "enter p " << std::endl; std::cin >> p; std:: cout << "enter q " << std::endl; std::cin >> q; n=p+q; std:: cout << " enter k larger than " << std::min(p,q) << " and smaller than " << n-1 << std::endl; std::cin >> k; srand(time(NULL)); VectorXf v1=VectorXf::Random(p); srand(time(NULL)); VectorXf v2=VectorXf::Random(q); VectorXf v3(n); v3 << v1, v2; std::sort(v3.data(),v3.data()+v3.size()); std::sort(v1.data(),v1.data()+v1.size()); std::sort(v2.data(),v2.data()+v2.size()); sol=nsmallest(v1.data(),v1.data()+v1.size(),v2.data(),v2.data()+v2.size(),k,std::less<float>()); //if it works, these two should return the same. std::cout << sol << std::endl; std::cout << v3(k) << std::endl; return 0; } ```