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 you have read our privacy policy.

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