Каков наилучший способ поиска наименьшего элемента больше 0 (или, возможно, вообще k) в векторе? - PullRequest
Новая
       8

Каков наилучший способ поиска наименьшего элемента больше 0 (или, возможно, вообще k) в векторе?

2 голосов
/ 13 января 2020

У меня была проблема, и одна ее часть требовала, чтобы я неоднократно находил наименьший элемент в векторе, пока все они не были равны 0. Код, который я использовал для этого, был следующим: 

    loop
        int minE = INT_MAX;
        for(int z = 0; z < arr.size(); z++) {
            if(arr[z] > 0) {
                if(arr[z] < minE) minE = arr[z];
            }
        }
        if(minE == INT_MAX) minE = 0; // I had a case to handle them being 0, so I turn them to 0 if all elements are <= 0
        // other things (subtract minE from all positive elements and count elements with that turn to 0)
    endloop

Теперь я понимаю, что, скорее всего, нет способа сделать это быстрее, чем линейное время, но мне было просто интересно, можно ли использовать какую-то функцию в STL чтобы достичь такого рода вещи, как min() from limits или lower_bound или min_element или что-то еще, может быть?

edit: Только что понял, что проблема в основном заключается в подсчете сортировки, или просто подсчет сортировки, или, может быть, какой-то Небольшая модификация, вопрос скорее в библиотечных функциях, чем в проблеме, поэтому не обращайте внимания на этот текст!

Ответы [ 3 ]

3 голосов
/ 13 января 2020

Если вы будете искать один и тот же вектор несколько раз, пока все они не станут 0, я бы порекомендовал отфильтровать вектор по нулевым значениям (принимает O (N)), затем отсортировал остальные (принимает O (NlogN), а затем только pop() элементов в постоянном времени от нижнего конца - это будет намного быстрее для больших массивов.

Вы можете фильтровать значения меньше или больше K на первом шаге, но не обязательно 0.

3 голосов
/ 13 января 2020

Эту проблему необходимо решить с помощью операции уменьшение , которая, кстати, также может быть аккуратно распараллелена.

В общем, вы можете соединить std::reduce с std::min. В вашем случае вам нужен функтор / лямбда, который вызывает std::min после проверки на нулевые значения.

В C ++ 20 вы также можете использовать view::filter для удаления нулевых значений из рассмотрения.

0 голосов
/ 13 января 2020

Если вы можете изменить порядок элементов в векторе, но не хотите изменять отдельные значения, тогда вы можете использовать алгоритмы кучи STL.

Сначала разделите ненулевые элементы вперед и ноль элементов в спину в O (N) времени. Затем выполните операцию make_heap с ненулевыми значениями, которая будет принимать O(numOfNonZeroElements), а затем повторно выполните pop_heap (занимает O(log(numOfNonZeroElements)) время) в этом диапазоне, который поместит передний элемент в заднюю часть ненулевого диапазона. а затем уменьшите ненулевой диапазон на 1. Общая сложность составляет O(n) + O(numOfNonZeroElements*log(numOfNonZeroElements)). 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

ostream& operator<< (ostream& out, const vector<int>& V)
{
    for (int e : V)
        out << e << ' ';
    return out;
}

int main()
{
    int n;
    cin >> n;

    vector<int> A(n);
    for (int& e : A)
        cin >> e;

    partition(A.begin(), A.end(), [](int e) { return e > 0; });
    cout << A << endl;

    vector<int>::iterator begin, end;
    begin = A.begin();
    for (end = A.begin(); end < A.end() && *end > 0; end = next(end));
    make_heap(begin, end, greater<int>());
    while (begin < end && A.front() > 0)
    {
        cout << A.front() << endl; // perform operation on A.front() here
        pop_heap(begin, end, greater<int>());
        cout << A << endl;
        end = prev(end);
    }
}
...