本文介绍了如何找到两个数组排序的工会第k最大元素？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我需要找到 K 最大元素在两个排序数组，但与一捻。
This算法假定 K＆LT; = MAX（M，N）和索引出差错时， K＆GT;最大（M，N） 。在我的问题我知道，这将永远是 K＆GT;（M + N）/ 2 ，因此 K＆GT;分（M，N）所以我需要改变儒勒Olléon的回答有点......我只是不明白这一点：〜
我发现这个链接第3页，但有错误出现（实施时，它不会返回正确的答案）
我知道一个快速解决方案是通过-1乘两个阵列，并采取k个最小的那工会和繁殖背答案-1但会令code无法读取。
这是的没有的一门功课。
好吧，我想我missunderstanding尼尔的答案或别的东西，因为这是我给他
的#include＆LT;算法＆GT;
＃包括＆LT; fstream的＆GT;
＃包括＆LT;的iostream＆GT;
＃包括＆LT; stdio.h中＆GT;
＃包括＆LT; stdlib.h中＆GT;
＃包括＆LT; time.h中＆GT;
＃包括＆LT;载体＆GT;
＃包括＆LT;艾根/密＆GT;
使用空间特征值;
使用本征:: VectorXf;
使用本征:: VectorXi;
浮动getNth（VectorXf＆安培; V1，VectorXf和放大器; V2，INT和放大器; N）{
INT步骤=（N / 4），的i1 =（N / 2），I2 =（正的i1）;
而（（2版（I2）＆GT;！= V1（i1-1）及＆安培;第一版（I1）＆GT; V2（i2-1）））{
如果（v1的（i1-1）＆GT; = V2（i2-1））{
i1- =步骤;
I2 + =步骤;
} 其他 {
I1 + =步骤;
i2- =步骤;
}
步骤/ = 2;
（！步骤），如果步= 1;
}
如果（V1（i1-1）＆GT; = V2（i2-1））
返回V1（i1-1）;
其他
返回V2（i2-1）;
}
诠释的main（）{
INT P，Q，N，K，L;
浮动溶胶;
性病::法院＆LT;＆LT; 输入p＆LT;＆LT;的std :: ENDL;
给std :: cin＆GT;＆GT;磷;
性病::法院＆LT;＆LT; 进入Q＆LT;＆LT;的std :: ENDL;
给std :: cin＆GT;＆GT; q;
N = P + Q;
性病::法院＆LT;＆LT; 进入ķ大于＆LT;＆LT;性病::分钟（P，Q）＆其中;＆其中; 且小于＆其中;＆其中; N-1＆LT;＆LT;的std :: ENDL;
给std :: cin＆GT;＆GT; K表;
K = N-K-1;
函数srand（时间（NULL））;
VectorXf V1 = VectorXf ::随机（对）;
函数srand（时间（NULL））;
VectorXf V2 = VectorXf ::随机（q）的;
VectorXf V3（N）;
V3＆LT;＆LT; V1，V2;
性病::排序（v3.data（），v3.data（）+ v3.size（），性病::更大＆LT;浮动＆GT;（））; //的std ::更大＆LT;浮动＆GT;（）
性病::排序（v1.data（），v1.data（）+ v1.size（），性病::更大＆LT;浮动＆GT;（））;
性病::排序（v2.data（），v2.data（）+ v2.size（），性病::更大＆LT;浮动＆GT;（））;
溶胶= getNth（V1，V2中，k）;
性病::法院＆LT;＆LT;溶胶LT;＆LT;的std :: ENDL;
性病::法院＆LT;＆LT; V3（K）＆LT;＆LT;的std :: ENDL;
返回0;
}
这是我所得到的：
输入p
12
输入q
32
进入k大超过12且小于43
13
nthoftwo：/Desktop/work/p1/geqw4/vi3/out/sp/c$c$c/eigen/Eigen/src/Core/DenseCoeffsBase.h:409：本征:: DenseCoeffsBase＆LT;衍生，1＆GT; ::标量和放大器;本征:: DenseCoeffsBase＆LT;衍生，1＆GT; ::运算符（）（征:: DenseCoeffsBase＆LT;衍生，1＆GT; ::指数）与衍生=本征::矩阵和LT;浮动，-0x00000000000000001，1＆gt;中征:: DenseCoeffsBase＆LT;衍生，1＆GT; ::标量=浮动，本征:: DenseCoeffsBase＆LT;衍生，1＆GT; ::指数=长整型]：断言`索引＆gt; = 0＆功放;＆安培;指数＆LT;大小（）'失败。
中止（核心转储）
如果您不熟悉征：错误是索引出引起 getNth（V1，V2，K）
修改
这是对JF塞巴斯蒂安简单而优雅的解决方案如下 - 所有的错误都是我的一个非常小的修改，但它似乎工作。这样做的目的是与原来的指标（即我不知道尼尔的想法是必不可少的）。
工作 的#include＆LT;算法＆GT;
＃包括＆LT; fstream的＆GT;
＃包括＆LT;的iostream＆GT;
＃包括＆LT; stdio.h中＆GT;
＃包括＆LT; stdlib.h中＆GT;
＃包括＆LT; time.h中＆GT;
＃包括＆LT;载体＆GT;
＃包括＆LT;＆了cassert GT;
＃包括＆LT;迭代器＆GT;
＃包括＆LT;艾根/密＆GT;
使用空间特征值;
使用本征:: VectorXf;
使用本征:: VectorXi;
模板＆LT;类RandomIterator，类比较＆GT;
类型名的std :: iterator_traits实现＆LT; RandomIterator＆GT; :: value_type的
nsmallest（RandomIterator firsta，RandomIterator lasta，RandomIterator firstb，RandomIterator lastb，为size_t N，比较少）{
断言（正＆其中;＆的static_cast所述;为size_t＆GT;（（lasta-firsta）+（lastb-firstb）））;
如果（firsta == lasta）收益*（firstb + N）;
如果（firstb == lastb）收益*（firsta + N）;
为size_t美达=（lasta-firsta）/ 2;
为size_t MIDB =（lastb-firstb）/ 2;
如果（（MIDA + MIDB）n种）
返回以下（*（firstb + MIDB），*（firsta + MIDA））？
nsmallest（firsta，lasta，firstb + MIDB + 1，lastb，正（MIDB + 1），更小）：
nsmallest（firsta +美达+ 1，lasta，firstb，lastb，正（MIDA + 1），更小）;
其他
返回以下（*（firstb + MIDB），*（firsta + MIDA））？
nsmallest（firsta，firsta +美达，firstb，lastb，N，少）：
nsmallest（firsta，lasta，firstb，firstb + MIDB，N，少）;
}
诠释的main（）{
INT P，Q，N，K，L;
浮动溶胶;
性病::法院＆LT;＆LT; 输入p＆LT;＆LT;的std :: ENDL;
给std :: cin＆GT;＆GT;磷;
性病::法院＆LT;＆LT; 进入Q＆LT;＆LT;的std :: ENDL;
给std :: cin＆GT;＆GT; q;
N = P + Q;
性病::法院＆LT;＆LT; 进入ķ大于＆LT;＆LT;性病::分钟（P，Q）＆其中;＆其中; 且小于＆其中;＆其中; N-1＆LT;＆LT;的std :: ENDL;
给std :: cin＆GT;＆GT; K表;
函数srand（时间（NULL））;
VectorXf V1 = VectorXf ::随机（对）;
函数srand（时间（NULL））;
VectorXf V2 = VectorXf ::随机（q）的;
VectorXf V3（N）;
V3＆LT;＆LT; V1，V2;
性病::排序（v3.data（），v3.data（）+ v3.size（））;
性病::排序（v1.data（），v1.data（）+ v1.size（））;
性病::排序（v2.data（），v2.data（）+ v2.size（））;
sol=nsmallest(v1.data(),v1.data()+v1.size(),v2.data(),v2.data()+v2.size(),k,std::less<float>());
//如果一切正常，这两个应该返回相同的。
性病::法院＆LT;＆LT;溶胶LT;＆LT;的std :: ENDL;
性病::法院＆LT;＆LT; V3（K）＆LT;＆LT;的std :: ENDL;
返回0;
}
解决方案
从您的意见我知道你想找到第k个最小值给予2负排序的数组，例如，对于 A = {5 ，4,3}，B = {2,1,0}; 和 K = 1 预期的结果是 0 即最小值 - 第一个最小值（这意味着 K 是 1 ）。
由于 nsmallest（）函数适用于排序数组，并接受定制的比较，你可以：
的#include＆lt;功能＆GT; //更大＆LT;＆GT;
＃包括＆LT;的iostream＆GT;
＃定义尺寸（A）（的sizeof（一）/的sizeof（* a））的
诠释的main（）{
诠释一个[] = {5,4,3};
INT B〔] = {2,1,0};
INT K = 1; //找到最小值，在第一最小值，B
INT I = K - 1; //转换为从零开始的索引
INT V = nsmallest（A，A + SIZE（a）中，B，B + SIZE（b）中，
尺寸（A）+尺寸（B）-1-i的，标准::更大＆其中; INT＆GT;（））;
性病::法院＆LT;＆LT; V＆LT;＆LT;的std :: ENDL; // - ＆GT; 0
返回伏;
}
我用 @尼尔的建议来解决这个指数和的答案：
的#include＆LT;＆了cassert GT;
＃包括＆LT;迭代器＆GT;
模板＆LT;类RandomIterator，类比较＆GT;
类型名的std :: iterator_traits实现＆LT; RandomIterator＆GT; :: value_type的
nsmallest（RandomIterator firsta，RandomIterator lasta，
RandomIterator firstb，RandomIterator lastb，
为size_t N，
比较少）{
断言（正＆其中;＆的static_cast所述;为size_t＆GT;（（lasta - firsta）+（lastb - firstb）））;
如果（firsta == lasta）收益*（firstb + N）;
如果（firstb == lastb）收益*（firsta + N）;
为size_t美达=（lasta - firsta）/ 2;
为size_t MIDB =（lastb - firstb）/ 2;
如果（（MIDA + MIDB）n种）
返回以下（*（firstb + MIDB），*（firsta + MIDA））？
nsmallest（firsta，lasta，firstb + MIDB + 1，lastb，正 - （MIDB + 1），更小）：
nsmallest（firsta +美达+ 1，lasta，firstb，lastb，正 - （MIDA + 1），更小）;
其他
返回以下（*（firstb + MIDB），*（firsta + MIDA））？
nsmallest（firsta，firsta +美达，firstb，lastb，N，少）：
nsmallest（firsta，lasta，firstb，firstb + MIDB，N，少）;
}
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 problemi 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 thatunion 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;
}
解决方案
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);
}
这篇关于如何找到两个数组排序的工会第k最大元素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！