c++ - Recursive Way to Find 2nd/3rd Smallest Element In Array -

-

below code written find smallest element of unsorted array in c++.

how should go editing recursive function find second or third smallest element in array?

i understand there other methods out there (i've searched), i'd know how using recursive function works 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;          = min(array,left,mid);         b = min(array,mid+1,right);          if (a<b)              return b;         else                      return a;     } }

many in advance

here attempt @ finding 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 1 line @ time. (enter -999 terminate)" << endl;      vector<int> array;  //      int input;      while(true){         cin >> input;         if(input == -999) //check termination condition         break;         array.push_back(input);     }      int imin;     int imax;      cout<<"enter imin, imax"<<endl;     cin>>imin;     cin>>imax;       cout<<"min number " << 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 && < c && < 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 < && b < c && b < d){             min = b;             if (a<c && <d)                 next_min = a;             else if (c < b && c < d)                 next_min = c;             else                 next_min = d;         }          if (c < && c < b && c < d) {             min = c;             if (b<a && b<d)                 next_min = b;             else if (a < b && < d)                 next_min = a;             else                 next_min = d;         }             if (d < && d < c && d < b){             min = d;             if (a<c && <b)                 next_min = a;             else if (c < b && c < a)                 next_min = c;             else                 next_min = b;         }          } }

this function find n smallest elements in recursive way, hope 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 = 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);     (int num : smallest3) {         cout << num << endl;     } }

brief explanation: n smallest elements in ascending order left & right half, call them leftresult , rightresult, merge two, picking next smallest element 2 partial results. merge sort, except return n elements instead of sorting whole array.


Comments

Post a Comment

Popular posts from this blog

c++ - Function signature as a function template parameter -

-
i'd use function signature template argument. works great classes, when try same trick function templates, msvc throws error: error c2768: 'func' : illegal use of explicit template arguments here's code: template <typename signature> void func(); template <typename r, typename a1> void func<r(a1)>(); what should make work? you cannot partially specialize function template, not supported language. can create partially specialized class template static member function, , possibly trampoline function instantiate class template , invoke static function. something this: namespace detail { template<typename signature> struct helper; template<typename r, typename a1> struct helper<r(a1)> { static void call() { // stuff r , a1... } }; } template<typename signature> void func() { detail::helper<signature>::call(); }
Read more

algorithm - What are some ways to combine a number of (potentially incompatible) sorted sub-sets of a total set into a (partial) ordering of the total set? -

-
i have sorting problem i'm pretty sure doesn't have canonical "answer" - has number of different approaches, each pros/cons. i'm interested in hearing different approaches. suppose bunch of people {p_i | i=1,...,m} ranking favorite ice cream flavors. in total there n different flavors, single person p_i ranks n_i << n flavors or familiar with. i'm interested in combining these sub-rankings plausible overall ranking of n flavors. for concrete situation: m , n both 1000 (by coincidence), , each n_i 20 . can assume there's enough overlap in flavors people rank such no flavor "isolated". again, i'm interested in hearing different ways approach this, if there isn't single clear answer. thanks! one way approach problem construct directed cyclic graph representing of constraints on ordering of elements. nodes in graph represent different elements compared , have edge first node second node if had ranked first e...
Read more

How to call a javascript function after the page loads with a chrome extension? -

-
there's function on page want call after loads. not own page, can't insert html it. can please provide specific examples how chrome extension or greasemonkey? (function submitaction() ). both chrome extensions , greasemonkey offer ways specify when script inject if executed. in chrome extension, you set in manifest : "content_scripts": [ { "run_at" : "document_idle", in greasemonkey compatible userscripts, set in metadata // @run-at document-end in both cases, have add script if want ensure resources loaded when function executed : document.addeventlistener('load', submitaction);
Read more