Медиана уникальных элементов вектора

190
04 февраля 2019, 04:30

Дан вектор std::vector<std::size_t>. Как наиболее эффективно получить медиану уникальных элементов вектора? Например, для вектора 1,6,3,1,5,1,2 -> 1,2,3,5,6 -> 3

На ум приходит только решение с копированием элементов вектора в std::set<std::size_t> и взятие цетрального элемента, но итератор не даёт сделать это за константу.

Answer 1

За константу вряд ли у вас что получится. Как я понимаю, вектор уже отсортирован? тогда 

v[(unique(v.begin(),v.end())-v.begin())/2]

за O(N)

Если вектор не отсортирован - то еще и сортировка; итого O(N log N)

Если четко известен диапазон значений и он небольшой - то блочная сортировка спасает - опять до O(N)

READ ALSO
Почему std::regex такой медленный?
c++

Почему std::regex такой медленный?

Попробую написать регулярное выражение, которое будет разбивать строку на отдельные словаНаписал такой код:

 181
Рандомное число в промежутке A и B
c++

Рандомное число в промежутке A и B

Написал программу в которой пользователь может задать числа А и В

 185
Цикл с локатором
Java

Цикл с локатором

Имею таблицу формата:

 246
Регулярное выражение много строчное
Java

Регулярное выражение много строчное

Здравствуй сообщество есть вот такая строка и регулярное выражение:

 214