Leetcode # 31. Next Permutation

https://leetcode.com/problems/next-permutation/

Solution

Step. 1
由最尾端找起，找到第一個下降的點 nums[i]

Step.2
如果 nums[i] 存在，則和 nums[j] 交換
$$\mathop{\arg\min}_{j > i}{\{nums[j]\,|\,nums[j]>nums[i]\}}$$

Step.3
將 nums[i + 1:] 給 reverse

Time Complexity: O(n)
Space Complexity: O(1)

class Solution:
  def nextPermutation(self, nums: List[int]) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """
    # Step 1
    i = len(nums) - 2
    while nums[i] >= nums[i + 1] and i > -1:
      i -= 1

    # Step 2
    if i >= 0:
      j = -1
      while nums[j] <= nums[i]:
        j -= 1
      nums[i], nums[j] = nums[j], nums[i]
      
    # Step 3
    left_len = len(nums) - i - 1
    for k in range(left_len // 2):
      nums[i + 1 + k], nums[-1 - k] = nums[-1 - k], nums[i + 1 + k]

Last Updated on 2023/08/16 by A1go