Sort Colors

Q: Что такое задача о голландском национальном флаге?

Эдсгер Дейкстра поставил такую задачу: даны объекты трёх цветов в ряд — красного, белого и синего, как на флаге Нидерландов. Сгруппируйте объекты каждого цвета за один проход, используя только обмены. Sort Colors — та же задача с числами 0, 1 и 2. Его решение — разбиение с тремя указателями low , mid и high .

Q: Какова временная и пространственная сложность сортировки цветов?

Решение за один проход работает за время O(n), поскольку на каждом шаге непрочитанная часть уменьшается на одну ячейку. Оно использует O(1) дополнительной памяти: три индекса и временное значение для обмена. Сортировка подсчётом имеет такие же оценки, но считывает массив дважды.

Q: Почему mid не перемещается после обмена с high?

Значение, которое возвращается из high , ещё ни разу не считывалось, поэтому это может быть 0, 1 или 2. Если переместить mid дальше него, посередине останется 0 или 2. Обмен с low — другое дело: между low и mid находятся только единицы, поэтому возвращаемое значение известно, и mid может двигаться дальше.

Q: Считающая сортировка — приемлемый ответ на задачу Sort Colors?

Это решение укладывается в ограничения O(n) по времени и O(1) по памяти, и многие интервьюеры принимают его в качестве первого ответа. Будь готов к дополнительному вопросу о выполнении за один проход — это задача о разбиении с тремя указателями. Подсчёт — лучший инструмент, когда цветов много, поскольку разбиение позволяет разделить элементы только на три группы.

СреднеДва указателя Сортировка

+10

Дан массив nums, в котором каждое значение — 0, 1 или 2. Представь, что это три цвета, например красный, белый и синий. Переставь элементы массива так, чтобы сначала шли все 0, затем все 1, а после них все 2, и верни его.

Реши задачу без функции сортировки из библиотеки. Суть в том, чтобы использовать свои знания о значениях.

Функция

sortColors(nums: integer-array) → integer-array

numsinteger-array: цвета, каждый из которых — 0, 1 или 2
Возвращаетinteger-array: те же значения: сначала все 0, затем все 1, затем все 2

Ограничения

1 ≤ nums.length ≤ 1.5 × 10⁴
Каждое 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.

+17 скрытых тестов при отправке

Дополнительный вопрос

Что бы вы изменили, если бы цветов было k вместо трёх, а k было намного меньше длины массива?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Любая сортировка задаёт нужный порядок, поэтому главный вопрос — что позволяют пропустить эти три значения. Поскольку могут встречаться только 0, 1 и 2, их можно подсчитать и переписать массив за два прохода. С помощью трёх указателей, отмечающих, где заканчиваются 0 и где начинаются 2, можно даже расставить все значения по местам за один проход. Это однопроходное разбиение — алгоритм национального флага Нидерландов.

Сортировка пузырьком вручную

Верно, но не успевает на самых больших тестах

Идея

Сортировка с помощью библиотеки работала бы за O(n log n), но условие задачи запрещает её, потому что интервьюер хочет увидеть, что вы будете делать с учётом того, что существует всего три значения. Тогда базовый вариант — сортировка, которую вы напишете сами, а проще всего правильно реализовать пузырьковую сортировку: пройти по массиву и каждый раз, когда два соседних элемента стоят не по порядку, поменять их местами.

За один проход наибольшее из встреченных значений перемещается в самый конец, словно пузырёк поднимается вверх. После первого прохода последняя позиция окончательно определена, после второго — последние две, поэтому n-1 проходов упорядочивают весь массив. В [2, 1, 0] первый проход перемещает 2 в конец, получая [1, 0, 2], а второй проход меняет местами 1 и 0.

Этот алгоритм медленный, потому что на каждом проходе сравнивается каждая пара, которая ещё не заняла окончательное положение: всего около n²/2 сравнений. При n = 1.5 × 10^4 это более 10^8 сравнений, плюс перестановка для каждой пары, которая изначально стоит не по порядку, и ни одна из этих операций не использует тот факт, что существует всего три значения.

Алгоритм

Выполни 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

Посчитай каждый цвет, затем перепиши

Идея

Пузырьковая сортировка тратит всё время на сравнение соседних элементов, но ты уже знаешь, какие значения есть в массиве. Если массив содержит два нуля, три единицы и две двойки, ответ известен ещё до того, как ты что-либо переместишь: два нуля, три единицы, две двойки. Важны только количества.

Поэтому один раз прочитай массив и подсчитай каждое значение. Затем перезапиши его с начала: 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

Один проход с тремя указателями (голландский национальный флаг)

Идея

При чтении формируй три области: 0 в начале, за ними 1, в конце 2, а между 1 и 2 — непрочитанная часть. Границы отмечают три индекса. Всё до low — это 0, всё от low до mid, не включая его, — это 1, всё после high — это 2, а от nums[mid] до nums[high] — ещё непрочитанная часть.

Прочитай nums[mid]. 1 уже находится в своей области, поэтому сдвинь mid дальше. 0 должен быть в начале: поменяй его местами с nums[low] и сдвинь дальше и low, и mid. Значение, которое приходит на место low, — это 1 (или тот же 0, если 1 ещё не встречалась), поэтому оно уже на месте. 2 должен быть в конце: поменяй его местами с nums[high] и сдвинь high назад, но оставь mid на месте, потому что значение, пришедшее с позиции high, ещё не прочитано.

На каждом шаге mid сдвигается вперёд или high — назад, поэтому непрочитанная часть каждый раз уменьшается на одну ячейку, и цикл завершается за n шагов. Проследи за [2, 0, 2]: первая 2 меняется местами с последней 2, а high уменьшается до 1; в индексе 0 по-прежнему находится 2, она меняется местами с 0, а high уменьшается до 0; теперь в индексе 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, когда high — индекс последнего непрочитанного элемента. Когда они совпадают, этот элемент всё ещё не прочитан. На [1, 0] цикл останавливается, не прочитав 0, и возвращает [1, 0].
Допускать, чтобы high становился меньше нуля при использовании беззнакового индекса. Массив, состоящий только из двоек, например [2], приводит к тому, что high становится равным -1. В Rust, где индексы имеют тип usize, вместо этого храните в high позицию на один элемент дальше непрочитанной части, как это сделано в коде на Rust.
Предполагать, что встречается каждый цвет. В [2, 0, 2] нет 1, и массив может содержать только один цвет. Правила для указателей справляются с обоими случаями без особых условий, поэтому не добавляйте их.

Частые вопросы4

Что такое задача о голландском национальном флаге?

Эдсгер Дейкстра поставил такую задачу: даны объекты трёх цветов в ряд — красного, белого и синего, как на флаге Нидерландов. Сгруппируйте объекты каждого цвета за один проход, используя только обмены. Sort Colors — та же задача с числами 0, 1 и 2. Его решение — разбиение с тремя указателями low, mid и high.

Какова временная и пространственная сложность сортировки цветов?

Решение за один проход работает за время O(n), поскольку на каждом шаге непрочитанная часть уменьшается на одну ячейку. Оно использует O(1) дополнительной памяти: три индекса и временное значение для обмена. Сортировка подсчётом имеет такие же оценки, но считывает массив дважды.

Почему mid не перемещается после обмена с high?

Значение, которое возвращается из high, ещё ни разу не считывалось, поэтому это может быть 0, 1 или 2. Если переместить mid дальше него, посередине останется 0 или 2. Обмен с low — другое дело: между low и mid находятся только единицы, поэтому возвращаемое значение известно, и mid может двигаться дальше.

Считающая сортировка — приемлемый ответ на задачу Sort Colors?

Это решение укладывается в ограничения O(n) по времени и O(1) по памяти, и многие интервьюеры принимают его в качестве первого ответа. Будь готов к дополнительному вопросу о выполнении за один проход — это задача о разбиении с тремя указателями. Подсчёт — лучший инструмент, когда цветов много, поскольку разбиение позволяет разделить элементы только на три группы.

Python

def sortColors(nums):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

nums = [2, 1, 0, 2, 0, 1, 1]

Ожидается

[0, 0, 1, 1, 1, 2, 2]

Sort Colors

Функция

Ограничения

Примеры

Подсказки

Решение

Сортировка пузырьком вручную

Посчитай каждый цвет, затем перепиши

Один проход с тремя указателями (голландский национальный флаг)

Ловушки и крайние случаи

Частые вопросы4

Похожие задачи