Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняТемы LeetCode44 статьи, давайте взглянем на 75 вопросов Leetcode, сортировка по цвету, сортировка по цвету.
Официальная сложность этого вопроса — «Средняя», с проходным баллом 45%, лайками 2955 и отклонениями 209 (данные международной версии).Из этих данных мы, вероятно, можем видеть, чтоНе слишком сложно, а лайков гораздо больше, чем неодобрения, что говорит о заголовкеочень хорошее качество. На самом деле, это правда, этот вопрос достаточно прост и достаточно интересен, чтобы им стоило заняться.
смысл названия
Дан массив из n элементов, каждый элемент массива представляет цвет. Есть три цвета: красный, белый и синий, которые представлены цифрами 0, 1 и 2 соответственно. Требуется отсортировать эти цвета по размеру и вернуть отсортированные результаты.
Требоватьне могу вызвать библиотеку сортировкисортировать, чтобы решить проблему.
сортировка ведра
Прочитав вопрос, вы должны это прочувствовать, если нет ограничения, что нельзя использовать сортировку, то этот вопрос не сложный. Даже если добавить ограничения, это несложно, раз уж мы не можем вызвать сортировку, то не можем ли мы написать свою сортировку? Для написания быстрой сортировки на Python требуется всего несколько строк.
Конечно, можно написать sort самостоятельно, очевидно, это крайняя мера. так какЭлемент только 3 значения, между ними существует всего несколько видов соотношения размеров, и сортировка совершенно не нужна. Легко подумать, что мы можем посчитать количество вхождений этих трех значений, нескольких нулей, нескольких единиц, нескольких двоек, а затем сложить эти числа вместе и восстановить предыдущие данные, верно?
Это работает, но на самом деле это схема сортировки, называемаясортировка по основанию, также известный как групповая сортировка, а некоторые места называются сортировкой в начальной школе (вероятно, это значение понятно учащимся начальной школы). Идея сортировки по основанию очень проста: мы создаем массив и используем каждый его бит, чтобы указать, появился ли элемент в исходном массиве. +1, если появится, 0, если не появится. После того, как мы пометим исходный массив, мы снова пройдем по отмеченному массиву.Поскольку индексы естественным образом упорядочены, мы можем получить отсортированный результат.
Неважно, если вы все еще немного запутались, мы поймем, написав код, из-за этой проблемы давайте предоставимinplaceметод, поэтому нам нужно переназначить элементы в числах в конце.
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
bucket = [0 for _ in range(3)]
for i in nums:
bucket[i] += 1
ret = []
for i in range(3):
ret += [i] * bucket[i]
nums[:] = ret[:]
По сравнению с сортировкой мы просто просматриваем данные дважды, первый раз — проходим по исходному массиву, чтобы получить числа 0, 1 и 2, а второй раз — заполняем полученные данные обратно в исходный массив. По сравнению с быстрой сортировкой или некоторыми другими алгоритмами сортировки
трудоемкая, сортировка ведромТолько дважды пересек массив, что значительно быстрее. Но, к сожалению, это не лучший метод, в заголовке ясно сказано, что есть метод, которому достаточно один раз пройтись по исходному массиву.
two pointers
Прежде чем мы представим конкретный алгоритм, давайте сначала проанализируем проблему. Так как цветов всего три, то когда мы закончим сортировку, весь массив будет разделен на три части, голова — 0, середина — 1, хвост — 2.
мы можемИспользуйте интервал, чтобы уменьшить диапазон 1, предполагая, что первый и последний элементы нашего текущего интервала равны l и r соответственно. Когда мы читаем 0, мы меняем его на l, затем перемещаем l на одно место назад. Когда мы читаем 2, мы меняем его местами с r, перемещая r на один бит влево. То есть мы гарантируем, что между l и r только 1 элемент.
Мы представили этот метод поддержания интервала ранее.Хотя оба поддерживают интервал, есть некоторые различия в работе. Алгоритм двух указателей, представленный ранее, также известный как метод линейки, по существу размещает новые элементы, перемещая правую границу интервала, и поддерживает допустимость всех элементов в интервале, перемещая левую границу для всплывающих данных. В современной практикеПервое, что вы получите, это недопустимый интервал., мы делаем это допустимым, обходя элементы и перемещая интервал. Есть некоторые тонкие различия в мышлении этих двух, но форма одна и та же, то есть для поддержания или достижения законности путем перемещения границ с левой и правой сторон.
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
l, r = 0, len(nums)-1
i = 0
while i < len(nums):
if i > r:
break
# 如果遇到0，则和左边交换
if nums[i] == 0:
nums[l], nums[i] = nums[i], nums[l]
l += 1
# 如果遇到2，则和右边交换
# 交换之后i需要-1，因为可能换来一个0
elif nums[i] == 2:
nums[r], nums[i] = nums[i], nums[r]
r -= 1
continue
i += 1
В этом методе, хотя мы и проходим массив только один раз, но из-заСлишком много обменов, общая скорость бега даже ниже, чем у описанного выше метода. Таким образом, обход массива дважды не обязательно хуже, чем однократный обход массива, в конце концов, оба
алгоритм, разница только константа. Количество обходов — это только одна часть того, что составляет константу.
В дополнение к этому методу у нас есть другие методы поддержания интервалов.
интервал технического обслуживания
Метод, который будет описан далее, очень изобретателен, и я лично думаю, что он даже более изобретателен, чем метод, описанный выше.
Представим такой сценарий, допустим, мы не оперируем данными на исходном массиве, а читаем данные из него и помещаем в новый массив. Давайте не будем думать о том, как поставить эту проблему на первое место, давайтеПредположим, что данные в нашем исходном массиве были размещены в нескольких, то как будет выглядеть новый массив в это время? Очевидно, что он должен быть отсортирован с несколькими нулями в начале, несколькими единицами в середине и несколькими двойками в конце.
Итак, вопрос в том, если мы читаем 0 в это время, как мы должны это выразить? Для упрощения описания нарисуем его в виде схемы:
Предположим, что синяя часть равна 0, зеленая часть равна 1, а розовая часть равна 2. a — самый правый нижний индекс 0, b — самый правый нижний индекс 1-й части, а c — самый правый нижний индекс 2-й части. Итак, в это время, когда нам нужно поставить 0, что нам делать?
С комбинацией диаграммы это легко понять, нам нужно поставить 0 на позицию а+1, тогда мыВам нужно переместить части 1 и 2 вправо на один пробел, сделайте пробел и поставьте 0. Очевидно, что накладные расходы на перемещение массива будут слишком велики, на самом деле не обязательно перемещать всю часть, нужно перемещать только головной и хвостовой элементы. Например, левая часть части 1 занята 0, поэтому, чтобы сохранить длину неизменной, правую часть тоже нужно удлинить на квадрат. Таким же образом правую часть части 2 тоже нужно удлинить на один квадрат. Затем вся операция выражается кодом: nums[a+1] = 0, nums[b+1] = 1, nums[c+1] = 2.
Предположим, что число, которое мы читаем, равно 1, тогда нам нужно увеличить b на одну единицу, но следствием этого является то, что часть 2 занята, поэтому 2 нужно увеличить, чтобы компенсировать единицу, занятую 1. Если вы читаете 2, вы можете просто расширить 2, потому что после 2 нет другого цвета.
Предположим, у нас есть пустой массив, мы можем это сделать, но на самом деле нам не нужно специально создавать массив, мы можемЗаполните себя оригинальным массивом. Поскольку число, которое мы читаем из исходного массива, совпадает с помещенным числом, мы сразу помещаем число в начало исходного массива и занимаем ранее считанное число.
Просто сказать это может быть немного запутанно, но это будет понятно сразу после просмотра кода:
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# 记录0，1和2的末尾位置
zero, one, two = -1, -1, -1
n = len(nums)
for i in range(n):
# 如果摆放0
# 那么1和2都往后平移一位，让一个位置出来摆放0
if nums[i] == 0:
nums[two+1] = 2
nums[one+1] = 1
nums[zero+1] = 0
zero += 1
one += 1
two += 1
elif nums[i] == 1:
nums[two+1] = 2
nums[one+1] = 1
one += 1
two += 1
else:
nums[two+1] = 2
two += 1
Суммировать
На этом решение этой проблемы в основном закончено.
Я верю, что каждый может это увидеть. С точки зрения сложности эта задача действительно несложная. Я верю, что каждый может найти решение, но все же немного сложно придумать оптимальное решение. С одной стороны, нужно очень глубоко разбираться в предмете, с другойтребует много размышлений. Для такого рода задач нет фиксированного решения, и нам нужно разработать решение в соответствии с требованиями задачи и реальной ситуацией.Это также самая большая проверка мыслительных способностей и способности разработки алгоритмов.Это намного интереснее, чем вопрос о том, будет ли алгоритм работать.
Я надеюсь, что каждый может получить удовольствие от этого вопроса.Если вам нравится эта статья, если вы можете, пожалуйстаобращать внимание, подбодрите меня и облегчите доступ к другим статьям.
В этой статье используетсяmdniceнабор текста