Ссылка на задачу - 2161. Partition Array According to Given Pivot.
В данной задаче нам предстоит реализовать базовую подзадачу Быстрой сортировки, но с дополнительным требованием сохранения относительного порядка, отчего стандартные методы реализации Q-sort нас не будут устраивать ☹
📌 Описание задачи
Дан массив nums и число pivot. Требуется переставить элементы массива так, чтобы:
- Все элементы меньше
pivot шли первыми.
- Все элементы равные
pivot находились в середине.
- Все элементы больше
pivot шли в конце.
- Относительный порядок элементов в каждой группе сохранялся.
💡 Идея
Мы хотим разделить массив на три части, не создавая лишние структуры данных.
Вместо этого заполним результирующий вектор напрямую, обрабатывая массив в три прохода.
🛠️ Детали подхода
1️⃣ Первый проход: добавляем в результат все элементы < pivot.
2️⃣ Подсчет и второй проход: вычисляем количество вхождений pivot в массиве и добавляем pivot в результат pivot_count раз.
3️⃣ Третий проход: добавляем все элементы > pivot в результат.
Используем Vec::with_capacity(nums.len()), чтобы избежать лишних аллокаций.
📊 Асимптотика
- Временная сложность:
O(n) — три прохода по nums.
- Дополнительная память:
O(1) — все данные хранятся только в результирующем массиве
(который всё же имеет размер O(n)).
💻 Исходный код
impl Solution {
pub fn pivot_array(nums: Vec<i32>, pivot: i32) -> Vec<i32> {
let mut result = Vec::with_capacity(nums.len());
// First pass: Collect elements smaller than pivot
result.extend(nums.iter().filter(|&&num| num < pivot));
// Count occurrences of pivot
let pivot_count = nums.iter().filter(|&&num| num == pivot).count();
// Insert pivot elements
result.extend(std::iter::repeat(pivot).take(pivot_count));
// Third pass: Collect elements greater than pivot using into_iter() to take ownership
result.extend(nums.into_iter().filter(|&num| num > pivot));
result
}
}
Tags: #rust #algorithms