0

Здравствуйте.

Подскажите, пожалуйста, как можно реализовать функцию, которая будет возвращать минимальные числа со сдвигом.

К примеру, есть массив элементов: 1, 2, 3, 4, 5, 6, 7, 8, 9, когда первый раз мы вызываем функцию поиска минимального, она возвращает, когда второй, то она уже будет игнорировать 1, когда третий раз, она будет игнорировать числа 1 и 2, и так до конца массива.

Я смог сделать только просто функцию поиска минимального числа, но он всё время возвращает одно и тоже минимальное число (в данном случае - 1).

3
  • @Angus123, Постарайтесь писать более развернутые вопросы. Поясните, в чем вы видите проблему, как ее воспроизвести и т. д. 27 фев 2015 в 18:24
  • передавайте в параметры игнорируемое значение и Ваш массив.
    – BuilderC
    27 фев 2015 в 18:28
  • А не проще использовать std::set или std::priority_queue? 7 мар 2015 в 7:02

2 ответа 2

1

Найти первые несколько минимумов просто. Однако солжнее найти n-й минимум.

Если вам нужно получать их последовательно, можно применить решение, которое советует @BuilderC: передать в функцию значение, полученное на предыдущем шаге, и игнорировать все элементы, меньшие этого значения.

Вот пример такого кода:

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

Если же вы не знаете предыдущий минимум, задача усложняется. По сути вам нужно найти k-ю порядковую статистику (это и есть k-й минимум), чем занимается алгоритм «медиана медиан (BFPRT)».

-2

на старом стандарте:

#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: демонстрация моего алгоритма специально для @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;
}
2
  • 1
    Это самое худшее, что можно посоветовать. Без пояснений, комментариев и т. д.Ну и что произойдет, если я захочу запустить это на двух массивах? 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; Сколько раз говорить людям, не используйте глобал! Так нет же, они еще и другим советуют...
    – Zelta
    28 фев 2015 в 10:03
  • можно вторым ввести второй параметр по умолчанию first с значением false для указания первого старта. cout << ReturnMin(v, false) << endl; а затем уже вызывать: cout << ReturnMin(v) << endl; т.е немного модифицировать мою функцию. в вопросе про второй массив ничего сказано не было. по вопросу и ответ. условия надо было точнее написать. @Zelta где вы глобальную переменную увидели?
    – perfect
    28 фев 2015 в 11:38

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.