Как найти k-й по величине элемент в объединении двух отсортированных массивов?
Мне нужно найтиk
самый большой элемент в двух отсортированных массивах, но с изюминкой.
это алгоритм предполагаетk<=max(m,n)
и индексы идут не так, когдаk>max(m,n)
, В моей проблеме
я знаю, что всегда будетk>(m+n)/2
и поэтомуk>min(m,n)
поэтому мне нужно немного изменить ответ Жюля Олля на ответ ... я просто не вижу, какой именно бит: ~
Я нашел этоссылка на сайт страница 3, но там есть ошибка (при реализации она не возвращает правильный ответ)
Я знаю, что быстрое решение было бы умножить оба массива на -1 и взять к наименьшее из этого объедините и умножьте ответ на -1, но это сделает код нечитаемым.
Этоnot домашнее задание
Хорошо, я думаю, что я неправильно понимаю ответ Нейла или что-то еще, потому что это то, что я даю «ему».
#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;
}
и вот что я получаю:
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)
если вы не знакомы с eigen: ошибка является индексом ошибки, вызваннойgetNth(v1,v2,k)
это очень незначительная модификация J.F. Sebastian 'apos; Простое и элегантное решение ниже - все ошибки мои, но, похоже, работает. Цель заключалась в том, чтобы работать с исходными индексами (т.е. я не уверен, что идея Нейла является необходимой).
#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;
}