next permutation 算法图解：下个排列 _排列

给定一个单词或整数数组，按字典顺序排列找到下一个排列例如，“gfg”的下一个排列是“ggf”，[1, 2, 3] 的下一个排列是 [1, 3, 2] 。
第一步：从后往前找到第一个破坏单调递增性质的位置（i，i+1）
第二步：在 i 后面找到位置最靠后比 A[i] 大的元素A[j]
【next permutation 算法图解：下个排列】第三步：交换 A[i] 和 A[j]
第四步：从 (i+1) 位置开始颠倒序列

文章插图

def nextPermutation(nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""n = len(nums)# step 1: find the larget i, such that A[i] < A[i+1]found = Falsefor i in range(n-2, -1, -1):if nums[i] < nums[i+1]:found = Truebreak# Notice: if can't find any, we have the largest permutationif not found: return nums.reverse()# step 2: find the largest index j, such that A[i] < A[j]for k in range(i+1, n):if nums[i] < nums[k]:j = k# step 3: swap i and jnums[i], nums[j] = nums[j], nums[i]# step 4: reverse A[i+1] to the endfor k in range(i+1, (i+n)//2+1):nums[k], nums[n+i-k] = nums[n+i-k], nums[k]return nums

Follow-up: 怎样找前一个排列呢？