Muszę znaleźćk największy element w dwóch posortowanych tablicach, ale z niespodzianką.

To algorytm zakładak<=max(m,n) a indeksy nie działająk>max(m,n). W moim problemie wiem, że zawsze tak będziek>(m+n)/2 i stądk>min(m,n) więc muszę trochę zmienić odpowiedź Julesa Olléona ... po prostu nie widzę, który bit: ~

Znalazłem topołączyć strona 3, ale jest tam błąd (po zaimplementowaniu nie zwraca właściwej odpowiedzi)

Wiem, że szybkie rozwiązanie polegałoby na pomnożeniu obu tablic przez -1 i przyjęciu najmniejszej wartości k tej unii i pomnożeniu odpowiedzi przez -1, ale to sprawi, że kod będzie nieczytelny.

To jestnie Praca domowa.

Ok, myślę, że nie rozumiem odpowiedzi Neila lub czegoś innego, ponieważ to właśnie daję mu „

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

i oto co otrzymuję:

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)

jeśli nie jesteś zaznajomiony z własnym: błąd jest indeksem poza błędem związanym zgetNth(v1,v2,k)

EDYTOWAĆ:

jest to bardzo drobna modyfikacja w prostym i eleganckim rozwiązaniu J.F. Sebastiana - wszystkie błędy są moje, ale wydaje się działać. Celem była praca z oryginalnymi indeksami (tj. Nie jestem pewien, czy pomysł Neila jest niezbędny).

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