Найти минимальные элементы в массиве

Question

Найти минимальные элементы в массиве

Рейтинг: 0Ответов: 1Опубликовано: 27.02.2015

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

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

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

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

c# массивы алгоритм

Источник: Stack Overflow на русском

Answer 1

▲ 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)».

Найти минимальные элементы в массиве

Ответы