Частичная сортировка: n-ые элементы в заданном порядке
Задача состоит в том, чтобы частично отсортировать вектор с дубликатами s.t. медиана (n-й элемент) находится в том положении, в котором она была бы, если бы вектор был отсортирован. Все меньшие элементы должны быть слева, все более крупные элементы справа. Все элементы со значением, равным медиане, должны быть в исходном порядке — но только это не остальные элементы.
Как бы вы решили это?
Мое первоначальное решение:
- Используйте std :: nth_element (), чтобы найти медианный элемент
- пройти через вектор и отсортировать только элементы со значением, равным медиане, относительно их индекса. Как бы я сделал это эффективно?
Решение
Используйте partition или stable_partition (чтобы сохранить исходный порядок).
class Predicate{
int median_value;
public:
Predicate(int med) : median_value(med) {}
bool operator()(int x){
return x < median_value;
}
};
int main(){
vector<int> v{ 10, 20, 30, 10, 30};
int median = 20;
cout << "median = " << median << endl;
stable_partition(v.begin(), v.end(), Predicate(median));
for ( auto i : v)
cout << i << " ";
}
Другие решения