Hello.

Tell me, please, how you can implement a function that will return the minimum numbers with a shift.

For example, there is an array of elements: 1, 2, 3, 4, 5, 6, 7, 8, 9, when the first time we call the search function is minimal, it returns when the second one , then it will already ignore 1, when the third time , it will ignore the numbers 1 and 2, and so on until the end of the array.

I could only do a simple function to find the minimum number, but it always returns the same minimum number (in this case, 1).

  • @ Angus123, Try to write more detailed questions. Explain what you see the problem, how to reproduce it, etc. - Nicolas Chabanovsky ♦
  • pass the ignored value and your array to the parameters. - BuilderC
  • Isn't it easier to use std :: set or std :: priority_queue? - VadimTukaev

2 answers 2

Find the first few lows easy. However, we must find the nth minimum.

If you need to get them sequentially, you can apply a solution that advises @BuilderC : pass the value obtained in the previous step to the function and ignore all elements smaller than this value.

Here is an example of such a code:

#include <iostream> #include <vector> using namespace std; template <typename T> T min_limited(T begin, T end, T ignore) { // Ѐункция Π²Π΅Ρ€Π½Π΅Ρ‚ ΡƒΠΊΠ°Π·Π°Ρ‚Π΅Π»ΡŒ Π½Π° наимСньший элСмСнт массива, // больший `ignore`, ΠΈΠ»ΠΈ ΡƒΠΊΠ°Π·Π°Ρ‚Π΅Π»ΡŒ Π·Π° послСдний элСмСнт массива. T min = end; for (; begin != end; ++begin) if (*begin > *ignore && (min == end || *begin < *min)) min = begin; return min; } int main() { vector<int> V = {1, 5, 2, 5, 6, 3}; auto min_val = min(V.begin(), V.end()); for (int i = 0; min_val != V.end(); ++i) { cout << "Min #" << i << ": " << *min_val << endl; min_val = min_limited(V.begin(), V.end(), min_val); } return 0; }

If you do not know the previous minimum, the task becomes more complicated. In fact, you need to find the k th order statistics (this is the k th minimum), what the median medians (BFPRT) algorithm does .

    on the old standard:

     #include <iostream> #include <vector> #include <algorithm> using namespace std; int ReturnMin(const vector<int> & v){ static bool first = false; static vector<int> heart; static int index = 0; if (!first){ first = true; heart = v; sort(heart.begin(), heart.end()); return heart[0]; } else return heart[++index]; } int main(){ vector<int> v; v.push_back(-1); v.push_back(3); v.push_back(-2); v.push_back(4); v.push_back(7); v.push_back(4); v.push_back(5); cout << ReturnMin(v) << endl; cout << ReturnMin(v) << endl; cout << ReturnMin(v) << endl; cout << ReturnMin(v) << endl; cout << ReturnMin(v) << endl; cout << ReturnMin(v) << endl; cout << ReturnMin(v) << endl; return 0; }

    UPD: demonstration of my algorithm specifically for @Zelta

     #include <iostream> #include <vector> #include <algorithm> using namespace std; int ReturnMin(const vector<int> & v, const bool first = true){ //static bool first = false; static vector<int> heart; static int index = 0; if (!first){ //first = true; index = 0; heart = v; sort(heart.begin(), heart.end()); return heart[0]; } else return heart[++index]; } int main(){ vector<int> v, v1; v.push_back(-1); v.push_back(3); v.push_back(-2); v.push_back(4); v.push_back(7); v.push_back(4); v.push_back(5); cout << ReturnMin(v, false) << endl; cout << ReturnMin(v) << endl; cout << ReturnMin(v) << endl; cout << ReturnMin(v) << endl; cout << ReturnMin(v) << endl; cout << ReturnMin(v) << endl; cout << ReturnMin(v) << endl; cout << "v1--->" << endl; v1.push_back(-1); v1.push_back(5); v1.push_back(-2); v1.push_back(5); cout << ReturnMin(v1, false) << endl; cout << ReturnMin(v1) << endl; cout << ReturnMin(v1) << endl; cout << ReturnMin(v1) << endl; return 0; }
    • one
      This is the worst that can be advised. Without explanations, comments, etc. Well, and what happens if I want to run it on two arrays? vector <int> v = {1, 2, 3}, x = {4, 5, 6}; cout << ReturnMin (v) << endl; cout << ReturnMin (v) << endl; cout << ReturnMin (v) << endl; cout << ReturnMin (x) << endl; cout << ReturnMin (x) << endl; cout << ReturnMin (x) << endl; How many times to speak to people, do not use global! But no, they also advise others ... - Zelta
    • You can enter the second second parameter by default first with the value false to indicate the first start. cout << ReturnMin (v, false) << endl; and then call: cout << ReturnMin (v) << endl; Ie a little to modify my function. nothing was said about the second array. for question and answer. conditions should have been more accurate to write. @Zelta where did you see the global variable? - perfect