Next Permutation

Q: Какова временная сложность алгоритма Next Permutation?

O(n) . Один проход справа находит опорный элемент, второй — значение, с которым нужно поменяться местами, а один разворот исправляет суффикс. Дополнительная память составляет O(1) , поскольку всё происходит внутри массива.

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

+10

Дан массив целых чисел nums; значения могут повторяться. Представь все различные перестановки этих значений, отсортированные в лексикографическом порядке: сравнивай две перестановки по первому индексу, на котором они различаются, и первой идёт та, у которой значение в этой позиции меньше. Верни перестановку, следующую за nums в этом порядке.

Если nums уже является наибольшей перестановкой, следующей за ней нет: верни наименьшую, в которой значения отсортированы по возрастанию. Стремись к временной сложности O(n) и дополнительной памяти O(1).

Функция

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

numsinteger-array: текущее расположение значений
Возвращаетinteger-array: следующее расположение в словарном порядке или значения, отсортированные по возрастанию, если nums — наибольший

Ограничения

1 ≤ nums.length ≤ 5000
0 ≤ nums[i] ≤ 1000

Примеры

Ввод: nums = [2, 5, 4, 1]
Вывод: [4, 1, 2, 5]
Пояснение: Хвост 5, 4, 1 убывает, поэтому число 2 перед ним должно увеличиться. Наименьшее значение в хвосте, превышающее 2, — это 4; поставь его на это место, а остальные расположи в возрастающем порядке: [4, 1, 2, 5].

Ввод: nums = [3, 2, 2, 1]
Вывод: [1, 2, 2, 3]
Пояснение: Весь массив уменьшается, поэтому это самая большая перестановка чисел 3, 2, 2 и 1. Ответ переходит к наименьшей перестановке: [1, 2, 2, 3].

Ввод: nums = [1, 5, 1]
Вывод: [5, 1, 1]
Пояснение: Первая 1 должна увеличиться. Последняя 1 равна ей, а не больше, поэтому единственное значение, которое может занять её место, — это 5, что даёт [5, 1, 1].

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

Как вместо этого найти предыдущую перестановку — ту, которая идет непосредственно перед nums в словарном порядке?

Решение

Убывающий суффикс уже настолько велик, насколько позволяют его значения, поэтому следующая перестановка изменяет значение непосредственно перед ним — опорный элемент. Увеличьте опорный элемент на минимально возможную величину, затем сделайте суффикс как можно меньше. Для этого нужны два прохода справа налево и одно обращение порядка элементов внутри массива.

Расположите элементы списка по порядку

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

Идея

Строим перестановки в глубину, начиная с отсортированных значений и всегда сначала пробуя наименьшее ещё не использованное значение. Так они получаются в лексикографическом порядке, поэтому ответ — первая перестановка, строго большая, чем nums; если такой нет, верните отсортированные значения. Повторяющиеся значения приводят к тому, что некоторые перестановки строятся дважды, как в последовательности 115, 151, 115, 151, 511, 511 для [1, 1, 5], но копия лишь повторяет одну из уже построенных, поэтому первая перестановка, которая больше, всё равно будет следующей.

Количество растёт как n!: для 12 различных значений существует 479,001,600 перестановок.

Алгоритм

Отсортируй копию nums в pool.
Строй перестановки в глубину, выбирая неиспользованные элементы pool слева направо.
Когда перестановка будет готова, сравни её с nums поэлементно.
Верни первую перестановку, которая больше, чем nums.
Если такой нет, верни pool.

def nextPermutation(nums):
    n = len(nums)
    pool = sorted(nums)  # taking the smallest unused value first gives sorted order
    used = [False] * n
    current = []

    def build():
        # True once current holds the first arrangement greater than nums
        if len(current) == n:
            return current > nums  # Python compares lists in dictionary order
        for i in range(n):
            if not used[i]:
                used[i] = True
                current.append(pool[i])
                if build():
                    return True
                current.pop()
                used[i] = False
        return False

    if build():
        return current
    return pool  # nothing is greater: nums was the largest arrangement

Найдите опорный элемент, поменяйте местами, разверните суффикс

Идея

Опорный элемент — это первое справа значение, которое меньше своего правого соседа: 2 в [2, 5, 4, 1]. Это крайняя справа позиция, которую можно увеличить, а увеличение самой правой возможной позиции обеспечивает наименьшее увеличение.

Поменяй опорный элемент местами с наименьшим значением в суффиксе, которое строго больше него. Суффикс убывает, поэтому это крайнее справа значение, большее опорного элемента: 4, в результате получается [4, 5, 2, 1]. Суффикс по-прежнему убывает, потому что старый опорный элемент подходит на место, где стояла 4. Теперь, когда первая часть стала больше, суффикс должен быть как можно меньше — идти по возрастанию; разворот убывающей последовательности даёт именно это: [4, 1, 2, 5].

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

Алгоритм

Присвойте i значение n-2 и перемещайте его влево, пока nums[i] ≥ nums[i + 1].
Если i ≥ 0, присвойте j значение n-1 и перемещайте его влево, пока nums[j] ≤ nums[i], затем поменяйте местами nums[i] и nums[j].
Разверните часть от i + 1 до конца, перемещая два индекса навстречу друг другу.
Верните nums.

def nextPermutation(nums):
    n = len(nums)
    # 1. the pivot is the last index whose value is smaller than the next one
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        # 2. swap it with the rightmost value that is larger than it
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    # 3. the suffix after the pivot is falling: reverse it to make it rising
    left, right = i + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1
    return nums

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

Использование > вместо ≥ при поиске опорного элемента. В [3, 2, 2, 1] пара 2, 2 не является возрастанием, и остановка на ней выбирает опорный элемент, который не может увеличиваться.
Обмен со значением, равным опорному элементу. В [1, 5, 1] обмен двух единиц ничего не меняет; ищите значение, строго большее опорного.
Обмен с наибольшим значением в суффиксе. В [2, 5, 4, 1] это перемещает 5 вперёд и пропускает все перестановки, начинающиеся с 4.
Пропуск случая, когда опорного элемента нет. Наибольшая перестановка должна вернуться отсортированной — для этого нужно развернуть весь массив.
В Rust индекс типа usize, начинающийся с n-2, вызывает панику при n = 1, а переход влево за 0 вызывает панику, если опорного элемента нет. Используйте знаковый индекс или отсчитывайте от 1.

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

Какова временная сложность алгоритма Next Permutation?

O(n). Один проход справа находит опорный элемент, второй — значение, с которым нужно поменяться местами, а один разворот исправляет суффикс. Дополнительная память составляет O(1), поскольку всё происходит внутри массива.

Почему вы переворачиваете суффикс вместо того, чтобы сортировать его?

После обмена суффикс всё ещё убывает, поэтому его реверсирование уже упорядочивает его по возрастанию. Реверсирование занимает O(n); сортировка даёт тот же результат за O(n log n).

Работает ли Next Permutation с повторяющимися значениями?

Да, при условии что оба сравнения считают равные значения не большими. Поиск опорного элемента пропускает равных соседей с ≥, а поиск элемента для обмена пропускает значения, равные опорному, с ≤. Тогда [1, 5, 1] превращается в [5, 1, 1] — следующую отличающуюся перестановку.

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

Тест #1

Тест #2

Тест #3

Аргумент

nums = [2, 5, 4, 1]

Ожидаемый вывод

[4, 1, 2, 5]