Нахождение n-го по величине элемента на месте
Мне нужно найти n-й по величине элемент в массиве, и в настоящее время я делаю это следующим образом:
std::vector<double> buffer(sequence); // sequence is const std::vector<double>
std::nth_element(buffer.begin(), buffer.begin() + idx, buffer.end(), std::greater<double>());
nth_element = buffer[idx];
Но есть ли способ найти n-й по величине элемент в массиве без использования внешнего буфера?
Решение
Вы можете избежать копирования всего буфера без изменения исходного диапазона, используя std::partial_sort_copy. Просто скопируйте частично отсортированный диапазон в меньший буфер размера nи возьмите последний элемент.
Если вы можете изменить исходный буфер, то вы можете просто использовать std::nth_element на месте.
Другие решения
Вы можете использовать функцию разделения, используемую в быстрой сортировке, чтобы найти n-й по величине элемент.
Функция разбиения разделит исходный массив на две части. Первая часть будет меньше, чем A [i], вторая часть будет больше, чем A [i], раздел вернет i.Если i равно n, то вернет A [i]. Если i меньше n, разделить вторую часть. Если i больше n, разделить первую часть.
Это не будет стоить вам дополнительного буфера, а средняя стоимость времени O (n).