Самый эффективный способ найти итераторы 4 максимальных значений в векторе const в C ++

Question

Мне нужно найти 4 самых больших числа в векторе const и вернуть их позиции. Я хочу, чтобы этот код имел лучшую временную и пространственную сложность. Моя первая идея - скопировать этот вектор const в вектор и отсортировать его по пузырькам 4 раза. Это дает мне 4 * N, но мне нужно создать вектор. Вторая идея - поместить все из этого константного вектора в priority_queue. Это дает мне временную сложность N * log2 (N) без создания других переменных. Максимальное значение N составляет около 100.

Есть ли какие-либо другие варианты, чтобы сделать это самым быстрым и наименее занимающим место способом?

РЕДАКТИРОВАТЬ: Не имеет значения, какой из них является самый большой, мне просто нужно вернуть положение этих 4 элементов во входном векторе.

Answer 1

Раствор O (n)

std::vector<int>::iterator max1 = v.begin(), max2 = v.begin(), max3 = v.begin(), max4 = v.begin();
for(std::vector<int>::iterator it = v.begin(); it != v.end(); it++) {
    if((*max1) < (*it)) {
        max4 = max3;
        max3 = max2;
        max2 = max1;
        max1 = it;
    } else if((*max2) < (*it)) {
        max4 = max3;
        max3 = max2;
        max2 = it;
    } else if((*max3) < (*it)) {
        max4 = max3;
        max3 = it;
    } else if((*max4) < (*it)) {
        max4 = it;
    }
}    

Answer 2

Вы можете довольно легко реализовать это с помощью дополнительного vector и алгоритма nth_element, который равен O(n) time:

std::vector<int> const v = ...;

// create a vector of elements with original indexes
std::vector<std::pair<int,int>> res;

// populate the result vector
int k = 0;
for (int i : v)
  res.push_back({i,k++});

// find the maximum 4 elements
std::nth_element(res.begin(), res.begin() + 4, res.end(),
   [](auto const &a, auto const &b) { return a.first > b.first; });

Вот демонстрация .

Обратите внимание, что в этом решении используется O(n) дополнительного места. Если N становится большим, это может быть неправильным подходом для поиска только 4 самых больших элементов. Это по-прежнему хороший подход, если вам нужны M самые большие элементы, где M растет как N.

Answer 3

Да, используйте кучу четвертого размера. Затем вы выполняете итерацию по вектору и соответственно обновляете кучу.

Пример кода с использованием методов std heap и нахождение минимальных значений ( отсюда ) следует. 1010 *

Адаптируйте соответственно:

• Используйте пару индекса, значение в куче, чтобы отслеживать позиции, которые вы хотите вернуть
• Используйте компаратор, который сравнивает значение в пара и устанавливает des c. заказ

Это более общий c, чем решение @Jugal Rawlani, если ваш номер n может измениться / вырасти в будущем. В противном случае его идея побеждает.

Answer 4

считайте 4 первых элемента в вектор из 4. отсортируйте этот вектор так, чтобы минимум 4 был в индексе 0.

l oop на оставшихся элементах вектора const, если текущее значение> min, замените его и пересортируйте вектор из 4 элементов