Найти в Дзене
Записки о Java
2 подписчика

LeetCode №31: Next Permutation: Как найти «следующее» число в порядке перестановок

2
1 мин
Условие задачи:
Реализуйте функцию, которая изменяет массив целых чисел на месте, чтобы получить следующую лексикографически большую перестановку.
Если такой перестановки не существует (массив в порядке убывания), верните наименьшую возможную перестановку (т.е. отсортированную по возрастанию). Примеры:[1,2,3] → [1,3,2]
[3,2,1] → [1,2,3]
[1,1,5] → [1,5,1]
[1,3,2] → [2,1,3]
Важно: Решение должно быть in-place (без дополнительной памяти, кроме O(1)).
Нельзя использовать встроенные функции для генерации перестановок.
Представь, что у тебя есть три кубика с цифрами: 1, 2, 3.
Ты выкладываешь их в разном порядке и читаешь как числа: Это все возможные «раскладки» — перестановки. Теперь ты смотришь на число 123 и спрашиваешь: «Какое самое ближайшее большее число я могу сделать из этих же кубиков?» Ответ: 132! А если у тебя 321 — самое большое?
Тогда «следующего» нет, и ты начинаешь сначала → 123. Ты просто ищешь следующий шаг в порядке от маленького к большому, как в алфавите! Алгоритм, пред
Оглавление
Рисунок: задача next permutation
Рисунок: задача next permutation

Введение

Условие задачи:
Реализуйте функцию, которая изменяет массив целых чисел на месте, чтобы получить следующую лексикографически большую перестановку.
Если такой перестановки не существует (массив в порядке убывания), верните наименьшую возможную перестановку (т.е. отсортированную по возрастанию).
Примеры:[1,2,3] → [1,3,2]
[3,2,1] → [1,2,3]
[1,1,5] → [1,5,1]
[1,3,2] → [2,1,3]
Важно: Решение должно быть in-place (без дополнительной памяти, кроме O(1)).
Нельзя использовать встроенные функции для генерации перестановок.

Объяснение для пятилетнего

Представь, что у тебя есть три кубика с цифрами: 1, 2, 3.
Ты выкладываешь их в разном порядке и читаешь как числа:

  • 123
  • 132
  • 213
  • 231
  • 312
  • 321

Это все возможные «раскладки» — перестановки.

Теперь ты смотришь на число 123 и спрашиваешь:

«Какое самое ближайшее большее число я могу сделать из этих же кубиков?»

Ответ: 132!

А если у тебя 321 — самое большое?
Тогда «следующего» нет, и ты начинаешь сначала → 123.

Ты просто ищешь следующий шаг в порядке от маленького к большому, как в алфавите!

Как это работает? Алгоритм (по шагам)

Алгоритм, предложенный Нараяной (и часто используемый в стандартных библиотеках), состоит из трёх шагов:

Шаг 1: Найди самый правый индекс i, такой что nums[i] < nums[i + 1]

→ Это место, где можно «увеличить» число, поменяв что-то справа.

Если такого i нет → массив в порядке убывания → просто переверни его.

Шаг 2: Найди самый правый индекс j > i, такой что nums[j] > nums[i]

→ Это наименьшее число справа от i, которое больше nums[i].

Шаг 3: Поменяй местами nums[i] и nums[j]

→ Теперь у нас «немного большее» начало.

Шаг 4: Переверни подмассив после i

→ Чтобы сделать хвост наименьшим возможным (т.к. он был в порядке убывания).

Решение на Java (с комментариями)

Рисунок: решение задачи часть 1
Рисунок: решение задачи часть 1
Рисунок: решение задачи часть 2
Рисунок: решение задачи часть 2
Рисунок: решение задачи часть 3
Рисунок: решение задачи часть 3

Пример работы: [1, 3, 2]

  1. Ищем i:3 >= 2 → пропускаем
    1 < 3 → i = 0
  2. Ищем j > 0, где nums[j] > 1:nums[2] = 2 > 1 → j = 2
  3. Меняем nums[0] и nums[2]: → [2, 3, 1]
  4. Переворачиваем после i=0 → подмассив [3, 1] → [1, 3]

→ Результат: [2, 1, 3]

Заключение

Пример, рассмотренный в статье, можно найти по адресу:

https://github.com/ShkrylAndrei/leetcode/blob/main/src/main/java/info/shkryl/task31_nextPermutation/Solution.java