2013. Следующая перестановка
Medium
4 решили
Дан массив целых чисел
Лексикографический порядок — как слова в словаре: массивы сравнивают слева направо. На первой позиции, где числа различаются, меньшее число даёт более раннюю перестановку. Поэтому
Для чисел 1, 2, 3 все перестановки по возрастанию такие:
Если текущая перестановка уже последняя (как
nums. Нужно переставить те же числа (набор не меняется) так, чтобы получилась следующая перестановка в лексикографическом порядке, и вернуть получившийся массив.Лексикографический порядок — как слова в словаре: массивы сравнивают слева направо. На первой позиции, где числа различаются, меньшее число даёт более раннюю перестановку. Поэтому
[1, 3, 2] идёт раньше [2, 1, 3].Для чисел 1, 2, 3 все перестановки по возрастанию такие:
[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]«Следующая» — соседняя строка сразу после текущей.
Если текущая перестановка уже последняя (как
[3, 2, 1]), замкните цикл: верните первую — числа в неубывающем порядке. Если числа повторяются, учитываются только различные перестановки того же набора.Примеры:
Вход:
[1, 2, 3]
Выход:
[1, 3, 2]
Объяснение: Все перестановки 1,2,3 по возрастанию: [1,2,3] → [1,3,2] → [2,1,3] → [2,3,1] → [3,1,2] → [3,2,1]. Сразу после [1,2,3] стоит [1,3,2].
Вход:
[1, 3, 2]
Выход:
[2, 1, 3]
Объяснение: В том же списке после [1,3,2] идёт [2,1,3].
Вход:
[3, 2, 1]
Выход:
[1, 2, 3]
Объяснение: [3,2,1] — последняя строка списка. Следующей нет, поэтому возвращаемся к первой: [1,2,3].
Вход:
[1, 1, 5]
Выход:
[1, 5, 1]
Объяснение: Различные перестановки: [1,1,5] → [1,5,1] → [5,1,1]. После [1,1,5] идёт [1,5,1].
Ограничения:
1 <= nums.length <= 100
0 <= nums[i] <= 100
Решите эту задачу в браузере
Создайте бесплатный аккаунт — редактор Python, Java, JavaScript и Go, проверка на тестах за секунды.
Комментарии (0)
Зарегистрируйтесь или войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!