c++ - 两个排序数组实现中的第 k 个元素

Question

我正在尝试适应 this c++ 在我的应用程序中实现著名的双排序数组算法的第 k 个元素(其中第二个数组按递增顺序排序)。现在，我可以看到两种解决方案:

1. 将B(第二个数组)元素的迭代器替换为reverse_iterator，
2. 尝试手动完成，例如用递减替换 B 指针的递增。

现在，我开始尝试 2) 并不是因为喜欢，而是因为我不太擅长使用 reverse_iterator。但是，我的“解决方案”不起作用。我想知道应该如何更改 J.F. Sebastian 的代码对第二个数组使用反向迭代器？

#include <cmath>
#include <ctime>
#include <functional>
#include <fstream>
#include <iostream>
#include <iterator>
#include <limits>
#include <vector>
#include <random>
#include <inttypes.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <numeric>

#define SIZE(a) (sizeof(a)/sizeof(*a))
#define NDEBUG 

using namespace std;
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){//https://stackoverflow.com/questions/4607945/how-to-find-the-kth-smallest-element-in-the-union-of-two-sorted-arrays/11698659#11698659 
    assert(std::is_sorted(firsta,lasta,less) && std::is_sorted(firstb,lastb,less));
    const float x_0=*firsta,x_1=*lastb;
    std::cout << x_0 << std::endl; 
    std::cout << x_1 << std::endl;
    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);
            }
        }
    }
}

主体的相关部分:

const int n=*nr,m=*mr,k=*kr-1;
int i;
float x[n];
srand (time(NULL));
for(i=0;i<n;i++)   x[i]=rand();
std::sort(x,x+m,std::greater<float>());
std::sort(x+m,x+n);
*vr=nsmallest_iter(x,x+m,x+m+1,x+n-1,n-2-k,std::greater<float>());

Answer 1

使用反向迭代器，您只需要对 link 中显示的代码进行一些小的调整。你提供了:

template<class RandomAccessIterator1, typename RandomAccessIterator2, class Compare>
typename std::iterator_traits<RandomAccessIterator1>::value_type
nsmallest_iter(RandomAccessIterator1 firsta, RandomAccessIterator1 lasta,
               RandomAccessIterator2 firstb, RandomAccessIterator2 lastb,
               size_t n,
               Compare less) {
   ...
}

和

int v = nsmallest_iter(
      a, a + SIZE(a),
      std::reverse_iterator<int*>(b + SIZE(b)), std::reverse_iterator<int*>(b),
      SIZE(a)+SIZE(b)-1-i,
      std::greater<int>());