如何找到两个数组排序的工会第k最大元素？

编程入门行业动态更新时间:2024-10-27 23:17:02

本文介绍了如何找到两个数组排序的工会第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 返回伏; }

我用 @尼尔的建议来解决这个指数和的 @ lambdapilgrim的为算法答案：

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

解决方案

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