Как найти первые 2 минимальных целых числа в массиве, используя дерево сегментов - PullRequest
Новая
       17

Как найти первые 2 минимальных целых числа в массиве, используя дерево сегментов

0 голосов
/ 17 февраля 2019

Как найти первые два минимальных элемента для запроса и обновления его.

На мой взгляд, я должен использовать сегментация (сегментное дерево)

Ответы [ 2 ]

0 голосов
/ 12 марта 2019

Это можно решить с помощью простой модификации дерева сегментов RMQ

Вот подход O (N log N):

  1. Построить дерево сегментов для данного массива
  2. Для каждого узла в дереве сегментов хранить минимальное значение для текущего диапазона и его индекса
  3. Обрабатывать запросы типа 1 следующим образом:
    • Найти минимальное значение в диапазоне [L, R] и егоindex
    • Найти минимальное значение в диапазонах [L, found_index-1] и [found_index + 1, R]
  4. Для запросов типа 2 достаточно обновить дерево сегментов
0 голосов
/ 17 февраля 2019

С <algorithm> кажется, вы ищете std::nth_element.Он будет следить за тем, чтобы элементы в желаемой позиции, второй элемент, был правильно размещен, но также следит за тем, чтобы элементы меньше, чем он, в данном случае первый элемент, находились слева от него.Все остальные элементы остаются в неуказанном порядке справа от позиции, которую вы хотели.Программа ниже: 

#include <algorithm>
#include <iostream>
#include <iterator>

int main() {
    using std::begin;
    using std::end;
    using std::next;

    int array[] = {5, 2, 1, 4, 3};

    std::copy(begin(array), end(array), std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';

    std::nth_element(begin(array), next(begin(array)), end(array));

    std::copy(begin(array), end(array), std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
}

выведет (на моей машине): 

5 2 1 4 3 
1 2 5 4 3
...