梅州建站推荐,帮别人做网站赚多少钱,网站建设与管理常用,wordpress网页优化1 问题
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如#xff0c;arr [1,2,3] #xff0c;以下这些都可以视作 arr 的排列#xff1a;[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地arr [1,2,3] 以下这些都可以视作 arr 的排列[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地如果数组的所有排列根据其字典顺序从小到大排列在一个容器中那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列那么这个数组必须重排为字典序最小的排列即其元素按升序排列。
例如arr [1,2,3] 的下一个排列是 [1,3,2] 。 类似地arr [2,3,1] 的下一个排列是 [3,1,2] 。 而 arr [3,2,1] 的下一个排列是 [1,2,3] 因为 [3,2,1] 不存在一个字典序更大的排列。 给你一个整数数组 nums 找出 nums 的下一个排列。
必须 原地 修改只允许使用额外常数空间。
示例 1
输入nums [1,2,3] 输出[1,3,2]
示例 2
输入nums [3,2,1] 输出[1,2,3]
示例 3
输入nums [1,1,5] 输出[1,5,1]
2 答案
这题直接不会字典序如何排列
官方解从后向前迭代数组
class Solution:def nextPermutation(self, nums: List[int]) - None:Do not return anything, modify nums in-place instead.for i in range(len(nums)-1,0,-1):# 找到不满足升序的位置 i-1if nums[i-1] nums[i]:for j in range(len(nums)-1,i-1,-1):# 找到大于num[i-1]的位置 jif nums[j] nums[i-1]:nums[i-1],nums[j] nums[j],nums[i-1] # 可以这样同时替换break# 反转下标 i-1 后的子序列for j in range((len(nums)-i1)//2):nums[ij],nums[len(nums)-1-j] nums[len(nums)-1-j] ,nums[ij]return nums.reverse() # 如果当前已经是最大则直接翻转成最小的return
