Sort Colors
Дан массив nums, в котором каждое значение — это 0, 1 или 2: три цвета, например красный, белый и синий. Переставь элементы массива так, чтобы сначала шли все 0, затем все 1, а потом все 2, и верни его. Реши задачу без библиотечной функции сортировки.
Функция
- numsinteger-array
- цвета, каждое значение — 0, 1 или 2
- Возвращаетinteger-array
- те же значения: сначала все 0, затем все 1, а потом все 2
Ограничения
1 ≤ nums.length ≤ 1.5 × 104- Каждый
nums[i]равен0,1или2. - Цвет может отсутствовать, а массив может содержать один цвет.
Примеры
- Ввод
- nums = [2, 1, 0, 2, 0, 1, 1]
- Вывод
- [0, 0, 1, 1, 1, 2, 2]
- Пояснение
- Массив содержит два 0, три 1 и два 2, поэтому результат именно такой: сначала два 0, затем три 1, потом два 2.
- Ввод
- nums = [2, 0, 2]
- Вывод
- [0, 2, 2]
- Пояснение
- Единицы вообще нет. Единственный 0 перемещается в начало, а за ним следуют две 2.
- Ввод
- nums = [1]
- Вывод
- [1]
- Пояснение
- Одно значение уже упорядочено, поэтому массив возвращается без изменений.
Дополнительный вопрос
Что бы вы изменили, если бы цветов было k вместо трёх, причём k было бы намного меньше длины массива?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Могут появиться только три разных значения. Что это позволяет сделать такого, чего не позволяет обычная сортировка?
Подсчёт 0, 1 и 2 и перезапись массива выполняются за два прохода. Представь, как за один проход одновременно растут три области: 0 — в начале, 2 — в конце, 1 — между ними.
Используйте три индекса:
low,midиhigh. Прочитайтеnums[mid]: при значении 0 выполните обмен сlow, при значении 2 — сhigh, а значение 1 оставьте на месте. После обмена сhighпрочитайте то же место ещё раз.
Решение
Могут встречаться только 0, 1 и 2, поэтому их можно подсчитать и переписать массив за два прохода. Три указателя, отмечающие границы нулей и начало двоек, позволяют сделать это за один проход, помещая каждое значение на своё место по мере чтения. Такое разбиение называется алгоритмом голландского национального флага.
Сортировка пузырьком вручную
Верно, но не успевает на самых больших тестах
Идея
Без сортировки с помощью библиотеки базовый вариант — написать сортировку самостоятельно. Сортировка пузырьком проходит по массиву и меняет местами соседние элементы, расположенные не по порядку. За каждый проход наибольшее встреченное значение перемещается в конец, поэтому после n-1 проходов все позиции окончательно определены.
Она выполняет около n²/2 сравнений: более 10^8 при n = 1.5 × 10^4, и ни одно из них не использует тот факт, что существует всего три значения.
Алгоритм
- Выполни n-1 проходов по массиву.
- На каждом проходе сравнивай каждую ещё не окончательную пару соседних элементов
nums[j]иnums[j + 1]и меняй их местами, если левый больше. - После прохода с номером
done(нумерация начинается с 0) последниеdone + 1позиций содержат окончательные значения, поэтому следующий проход останавливается перед ними. - Верни
nums.
def sortColors(nums):
n = len(nums)
for done in range(n - 1):
# One pass: the largest value left so far bubbles to index n-1-done.
for j in range(n - 1 - done):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return numsПосчитайте каждый цвет, затем перепишите
Идея
Равные значения взаимозаменяемы, поэтому важны только их количества. В первом примере два 0, три 1 и два 2 определяют ответ ещё до того, как ты что-либо переместишь.
Один раз пройдись по массиву и подсчитай количество каждого значения, затем перезапиши его с начала: count[0] нулей, count[1] единиц, count[2] двоек. Это сортировка подсчётом. Два прохода и три счётчика дают время O(n) и дополнительную память O(1).
Алгоритм
- Создай три счётчика, все равны 0.
- Прочитай каждое значение и прибавь единицу к соответствующему счётчику.
- Запиши
count[0]нулей с начала, затемcount[1]единиц, затемcount[2]двоек. - Верни
nums.
def sortColors(nums):
count = [0, 0, 0] # how many 0s, 1s and 2s
for x in nums:
count[x] += 1
i = 0
for color in range(3):
for _ in range(count[color]):
nums[i] = color
i += 1
return numsОдин проход с тремя указателями (голландский национальный флаг)
Идея
Поддерживай три области по мере чтения. Всё до low — это 0, всё от low до mid, не включая его, — это 1, всё после high — это 2, а элементы от nums[mid] до nums[high] ещё не прочитаны.
Прочитай nums[mid]. 1 уже находится в своей области, поэтому сдвинь mid дальше. 0 меняется местами с nums[low], и оба указателя сдвигаются дальше: значение, которое возвращается с позиции low, — это 1 или, если 1 ещё не встречалась, тот же 0, поэтому оно уже на месте. 2 меняется местами с nums[high], а high сдвигается назад, но mid остаётся на месте, потому что значение, пришедшее с позиции high, ещё не прочитано.
На каждом шаге mid сдвигается вперёд или high — назад, поэтому цикл завершится за n шагов. Для [2, 0, 2] первая 2 меняется местами с последней, и high уменьшается до 1; индекс 0 по-прежнему содержит 2, которая меняется местами с 0; затем 0 остаётся на месте, и получается [0, 2, 2].
Алгоритм
- Установите
low = 0,mid = 0иhighравным последнему индексу. - Пока
mid ≤ high, считывайтеnums[mid]. - Если это 0, поменяйте его местами с
nums[low]и переместитеlowиmidна один шаг вправо. - Если это 1, переместите
midна один шаг вправо. - Если это 2, поменяйте его местами с
nums[high]и переместитеhighна один шаг влево. Оставьтеmidна месте. - Верните
nums.
def sortColors(nums):
# nums[:low] are 0s, nums[low:mid] are 1s, nums[high + 1:] are 2s.
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
# The value swapped in from high is unread, so mid stays.
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
return nums
Ловушки и крайние случаи
- Продвигать
midвперед после обмена сhigh. Прибывшее значение еще не прочитано: в[1, 2, 0]2 меняется местами с 0, и пропуск 0 возвращает[1, 0, 2]. - Выполнять цикл, пока
mid < high. Когда они встречаются, эта ячейка все еще не прочитана: для[1, 0]цикл останавливается, не прочитав 0, и возвращает[1, 0]. - Допускать, чтобы
highопускался ниже нуля при использовании беззнакового индекса. Массив, состоящий только из двоек, например[2], приводит к тому, чтоhighстановится равным -1, что вызывает переполнение типаusizeв Rust. Вместо этого оставляйтеhighна единицу дальше непрочитанной части.
Частые вопросы3
Что такое задача о голландском национальном флаге?
Эдсгер Дейкстра сформулировал задачу так: расположить в ряд объекты трёх цветов — красного, белого и синего, как на флаге Нидерландов, — чтобы объекты каждого цвета были сгруппированы, за один проход, используя только обмены. Задача «Сортировка цветов» — это та же задача с числами 0, 1 и 2, а его решение — разбиение с тремя указателями.
Какова временная и пространственная сложность сортировки цветов?
Однопроходное решение работает за время O(n), потому что на каждом шаге непрочитанная часть сокращается на одну ячейку. Оно использует O(1) дополнительной памяти: три индекса и временное значение для обмена. Сортировка подсчётом имеет такие же оценки, но считывает массив дважды.
Подходит ли сортировка подсчётом в качестве ответа на задачу «Сортировка цветов»?
Он соответствует ограничениям O(n) по времени и O(1) по памяти, и многие интервьюеры принимают его в качестве первого ответа. Затем будьте готовы к просьбе выполнить проход за один раз. Подсчёт — более подходящий инструмент, когда цветов много, поскольку разбиение делит элементы только на три группы.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
def sortColors(nums):
# Напишите код здесьТест #1
Тест #2
Тест #3
Аргумент
nums = [2, 1, 0, 2, 0, 1, 1]
Ожидаемый вывод
[0, 0, 1, 1, 1, 2, 2]