递归的方式找到第二/第三最小的元素数组 [英] Recursive Way to Find 2nd/3rd Smallest Element In Array
本文介绍了递归的方式找到第二/第三最小的元素数组的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
下面是一个code写我发现在C ++中排序的数组的最小元素。
我应该如何去编辑我的递归函数找到数组中的第二个，甚至第三个最小的元素？
据我了解有其他方法在那里（我搜索），但是我想知道如何使用递归函数像这样该协会致力于只是最低数量做到这一点。
INT分钟（矢量＆lt;＆INT GT;＆安培;阵，INT和放大器;分钟，INT和放大器; next_min，诠释左，右诠释）
{
int类型的;
INT B： 如果（左右==）{
返回数组[左]
}其他{
INT中旬=（右+左）/ 2; A =分钟（阵，左，中）;
B =分钟（排列，中期+ 1，右）; 如果（A＆LT; B）
返回b;
其他
返回;
}
}
提前感谢
下面是我试图找到第二个最小的：
＃包括LT＆;＆iostream的GT;
＃包括LT＆;矢量＆GT;
＃包括LT＆; cstdlib＆GT;使用命名空间std;INT计数器= 0;无效MINF（矢量＆lt;＆INT GT;＆安培;阵，诠释左，右INT，INT和放大器;分钟，INT和放大器; next_min）;诠释的main（）
{
INT next_min; COUT＆LT;＆LT; 一次输入整数一行（输入-999终止）。＆LT;＆LT; ENDL; 矢量＆lt;诠释＆GT;阵列; //
INT输入; 而（真）{
CIN＆GT;＆GT;输入;
如果（输入== -999）//检查终止条件
打破;
array.push_back（输入）;
} INT爱民;
INT IMAX; COUT＆LT;＆LT;输入爱民，那么IMAX＆LT;＆LT; ENDL;
CIN＆GT;＆GT;爱民;
CIN＆GT;＆GT; IMAX; COUT＆LT;＆LT;最小号码是＆LT;＆LT; next_min＆LT;＆LT; ENDL; cin.get（）;
系统（暂停）;
返回0;
}无效MINF（矢量＆lt;＆INT GT;＆安培;阵，诠释左，右INT，INT和放大器;分钟，INT和放大器; next_min）
{
int类型的;
INT B：
INT℃;
INT D组; 如果（左右==）{
分=阵列[左]
next_min = 2147483647;
}其他{
INT中旬=（右+左）/ 2; MINF（阵，左，中，A，B）;
MINF（排列，中期+ 1，右，C，D）; 如果（A＆LT; B和;＆安培; A＆LT; C＆放大器;＆安培; A＆LT; d）{
分=一;
如果（B＆LT; C＆功放;和B＆LT; D）
next_min = B;
否则，如果（C＆LT; B和;＆安培; C＆LT; D）
next_min = C;
其他
next_min = D;
} 如果（B＆LT; A和和B＆LT; C＆功放;和B＆LT; d）{
分= B;
如果（一个c为C＆放大器;＆放大器;一个与所述; D）
next_min =一;
否则，如果（C＆LT; B和;＆安培; C＆LT; D）
next_min = C;
其他
next_min = D;
} 如果（C＆LT; A和＆功放; C＆LT; B和;＆安培; C＆LT; d）{
分= C;
如果（B＆LT; A和和B＆LT; D）
next_min = B;
否则，如果（A＆LT; B和;＆安培; A＆LT; D）
next_min =一;
其他
next_min = D;
} 如果（D＆下;一个与放大器;和D c为C＆放大器;和D＆下; B）{
分= D;
如果（一个c为C＆放大器;＆放大器;一个与所述; B）
next_min =一;
否则如果（℃下B和;＆放大器;℃下一个）
next_min = C;
其他
next_min = B;
}
}
}
解决方案
这是会发现一个函数 N 以递归的方式最小元素，希望它帮助！
的#include＆LT;矢量＆GT;
＃包括LT＆;＆iostream的GT;使用命名空间std;矢量＆lt;诠释＆GT; NMIN（常量矢量＆lt;＆INT GT;＆安培;数组，整数N，诠释左，右诠释）{
矢量＆lt;诠释＆GT;结果;
如果（左右==）{
result.push_back（数组[左]）;
}其他{
INT中旬=（右+左）/ 2;
矢量＆lt;诠释＆GT; leftResult = NMIN（数组，正，左，中）;
矢量＆lt;诠释＆GT; rightResult = NMIN（数组，N，年年+ 1，右）;
INT I = 0;
int类型l = 0;
INT R = 0;
INT L = leftResult.size（）;
INT R = rightResult.size（）;
而（ⅰ＆所述; N＆放大器;及（L＆下：L ||为r，R））{
我++;
如果（L＆下：L）{
如果（为r R） - {
如果（leftResult [1]; rightResult [R]）{
result.push_back（leftResult [L ++]）;
}其他{
result.push_back（rightResult [R ++]）;
}
}其他{
result.push_back（leftResult [L ++]）;
}
}其他{
result.push_back（rightResult [R ++]）;
}
}
}
返回结果;
}诠释主（）{
矢量＆lt;诠释＆GT;测试= {-2，6,7，1，3，7，4,2，5,0，8，-2};
矢量＆lt;诠释＆GT; smallest3 = NMIN（测试，3,0，test.size（） - 1）;
对于（INT NUM：smallest3）{
COUT＆LT;＆LT; NUM＆LT;＆LT; ENDL;
}
}
简要说明：获得高达 N 按升序最小元素从左边和放大器;右半边，称他们为 leftResult 和 rightResult ，然后合并这两个，总是从两个部分选择下一个最小的元素结果。这就好比归并排序，但它只会返回到ñ 元素而不是整个数组排序。
Below is a code I written to find the smallest element of an unsorted array in C++.
How should I go about editing my recursive function to find the second or even the third smallest element in the array?
I understand there are other methods out there (I've searched), however I'd like to know how to do it using a recursive function like this which works for just the minimum number.
int min(vector<int> &array, int &min, int &next_min, int left,int right)
{
int a;
int b;
if(left == right) {
return array[left];
} else {
int mid= (right+left)/2;
a = min(array,left,mid);
b = min(array,mid+1,right);
if (a<b)
return b;
else
return a;
}
}
Many thanks in advance
Here is my attempt at finding the 2nd smallest:
#include<iostream>
#include<vector>
#include <cstdlib>
using namespace std;
int counter=0;
void minf(vector<int> &array,int left,int right,int &min, int &next_min);
int main()
{
int next_min;
cout << "Enter integers one line at a time. (Enter -999 to terminate)" << endl;
vector<int> array; //
int input;
while(true){
cin >> input;
if(input == -999) //check for termination condition
break;
array.push_back(input);
}
int imin;
int imax;
cout<<"Enter imin, then imax"<<endl;
cin>>imin;
cin>>imax;
cout<<"Min number is " << next_min <<endl;
cin.get();
system("pause");
return 0;
}
void minf(vector<int> &array,int left,int right,int &min, int &next_min)
{
int a;
int b;
int c;
int d;
if(left == right) {
min = array[left];
next_min = 2147483647;
} else {
int mid= (right+left)/2;
minf(array,left,mid,a,b);
minf(array,mid+1,right,c,d);
if (a < b && a < c && a < d) {
min = a;
if (b<c && b <d)
next_min = b;
else if (c < b && c < d)
next_min = c;
else
next_min = d;
}
if (b < a && b < c && b < d){
min = b;
if (a<c && a <d)
next_min = a;
else if (c < b && c < d)
next_min = c;
else
next_min = d;
}
if (c < a && c < b && c < d) {
min = c;
if (b<a && b<d)
next_min = b;
else if (a < b && a < d)
next_min = a;
else
next_min = d;
}
if (d < a && d < c && d < b){
min = d;
if (a<c && a <b)
next_min = a;
else if (c < b && c < a)
next_min = c;
else
next_min = b;
}
}
}
解决方案
This is a function which will find the n smallest elements in a recursive way, hope it helps!
#include <vector>
#include <iostream>
using namespace std;
vector<int> nMin(const vector<int> &array, int n, int left, int right) {
vector<int> result;
if (left == right) {
result.push_back(array[left]);
} else {
int mid = (right + left) / 2;
vector<int> leftResult = nMin(array, n, left, mid);
vector<int> rightResult = nMin(array, n, mid + 1, right);
int i = 0;
int l = 0;
int r = 0;
int L = leftResult.size();
int R = rightResult.size();
while (i < n && (l < L || r < R)) {
i++;
if (l < L) {
if (r < R) {
if (leftResult[l] < rightResult[r]) {
result.push_back(leftResult[l++]);
} else {
result.push_back(rightResult[r++]);
}
} else {
result.push_back(leftResult[l++]);
}
} else {
result.push_back(rightResult[r++]);
}
}
}
return result;
}
int main() {
vector<int> test = {-2, 6, 7, 1, 3, 7, 4, 2, 5, 0, 8, -2};
vector<int> smallest3 = nMin(test, 3, 0, test.size() - 1);
for (int num : smallest3) {
cout << num << endl;
}
}
Brief explanation: Get up to n smallest elements in ascending order from the left & right half, call them leftResult and rightResult, then merge the two, always picking the next smallest element from the two partial results. This is like merge sort, except that it will only return up to n elements instead of sorting the whole array.
这篇关于递归的方式找到第二/第三最小的元素数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
