Сложность: medium
Дан массив nums, содержащий n объектов, окрашенных в красный, белый или синий цвет. Отсортируйте их на месте так, чтобы объекты одного цвета находились рядом, а цвета располагались в порядке красный, белый и синий.
Мы будем использовать целые числа 0, 1 и 2 для обозначения красного, белого и синего цветов соответственно.
Вы должны решить эту задачу без использования функции сортировки библиотеки.
Пример:
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
👨💻 Алгоритм:
1⃣Инициализация крайней правой границы нулей: p0 = 0. Во время выполнения алгоритма nums[idx < p0] = 0.
2⃣Инициализация крайней левой границы двоек: p2 = n - 1. Во время выполнения алгоритма nums[idx > p2] = 2.
3⃣Инициализация индекса текущего элемента для рассмотрения: curr = 0.
Пока curr <= p2:
Если nums[curr] = 0: поменять местами элементы с индексами curr и p0, и сдвинуть оба указателя вправо.
Если nums[curr] = 2: поменять местами элементы с индексами curr и p2. Сдвинуть указатель p2 влево.
Если nums[curr] = 1: сдвинуть указатель curr вправо.
😎 Решение:
function sortColors(&$nums) {
$p0 = 0;
$curr = 0;
$p2 = count($nums) - 1;
while ($curr <= $p2) {
if ($nums[$curr] === 0) {
// Swap elements at indices curr and p0
$temp = $nums[$curr];
$nums[$curr] = $nums[$p0];
$nums[$p0] = $temp;
$curr++;
$p0++;
} elseif ($nums[$curr] === 2) {
// Swap elements at indices curr and p2
$temp = $nums[$curr];
$nums[$curr] = $nums[$p2];
$nums[$p2] = $temp;
$p2--;
} else {
$curr++;
}
}
}Ставь 👍 и забирай 📚 Базу знаний