Проблема
Реализация Следующая перестановка , который переставляет числа в лексикографически следующую большую перестановку чисел.
Если такое расположение невозможно, оно должно изменить его как самый низкий возможный порядок (то есть отсортированный в порядке возрастания).
Замена должна быть на месте и использовать только постоянную дополнительную память.
Пример 1:
Input: nums = [1,2,3] Output: [1,3,2]
Пример 2:
Input: nums = [3,2,1] Output: [1,2,3]
Пример 3:
Input: nums = [1,1,5] Output: [1,5,1]
Пример 4:
Input: nums = [1] Output: [1]
Ограничения:
1. длиной0 [i]
Тесты
import pytest
from .Day31_NextPermutation import Solution
s = Solution()
@pytest.mark.parametrize(
"nums,expected",
[
([1, 2, 3], [1, 3, 2]),
([3, 2, 1], [1, 2, 3]),
([1, 1, 5], [1, 5, 1]),
([1], [1]),
],
)
def test_next_permutation(nums, expected):
s.nextPermutation(nums)
assert nums == expected
Решение
from typing import List
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
i = len(nums) - 2
while i >= 0 and nums[i + 1] <= nums[i]:
i -= 1
if i >= 0:
j = len(nums) - 1
while j >= 0 and nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
k = len(nums) - 1
while i < k:
i += 1
nums[i], nums[k] = nums[k], nums[i]
k -= 1
Анализ
Оригинал: “https://dev.to/ruarfff/day-31-next-permutation-5d2j”