Дан массив nums с n объектами, окрашенными в красный, белый или синий цвет, отсортируйте их на месте, чтобы объекты одного цвета были смежными, а цвета располагались в следующем порядке: красный, белый и синий. синий.
Мы будем использовать целые числа 0, 1 и 2 для представления красного, белого и синего цветов соответственно.
Вы должны решить эту проблему, не используя библиотечную функцию сортировки.
Пример 1:
Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2]
Пример 2:
Input: nums = [2,0,1] Output: [0,1,2]
Ограничения:
n == nums.length1 <= n <= 300nums[i]равно0,1или2.
Дополнение. Не могли бы вы придумать однопроходный алгоритм, использующий только постоянное дополнительное пространство?
Решение
Временная сложность O (n log n)
Пробел О(1)
Временная сложность O(n log n)
Пространственная сложность O(n)
Временная сложность O(2n)
Пространственная сложность O(1)
Временная сложность O(2n)
Пространственная сложность O(1)
Вы видите эту зеленую кнопку подписки? 🐌
