LeetCode——31. 下一个排列
程序员文章站
2022-04-28 20:41:16
31. 下一个排列题目实现获取 下一个排列 的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。必须 原地 修改,只允许使用额外常数空间。 示例 1:输入:nums = [1,2,3]输出:[1,3,2]示例 2:输入:nums = [3,2,1]输出:[1,2,3]示例 3:输入:nums = [1,1,5]输出:[1,5,1]示例 4:输入:nums = [1]输出:[...
31. 下一个排列
题目
实现获取 下一个排列 的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须 原地 修改,只允许使用额外常数空间。
示例 1:
输入:nums = [1,2,3]
输出:[1,3,2]
示例 2:
输入:nums = [3,2,1]
输出:[1,2,3]
示例 3:
输入:nums = [1,1,5]
输出:[1,5,1]
示例 4:
输入:nums = [1]
输出:[1]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/next-permutation
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解思路
1>源代码
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
length = len(nums)
i = length-2
while i>=0 and nums[i]>=nums[i+1]:
i-=1
if i>=0:
j = length-1
while j>=0 and nums[j]<=nums[i]:
j-=1
nums[j], nums[i] = nums[i], nums[j]
left = i+1
right = length-1
while left<right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
2>算法介绍
本题其实是一道找规律的题,我们以[4, 6, 5, 2, 3, 1]的下一次排列为例,很明显他的下一次排列是[4, 6, 3, 1, 2],主要思路是:
首先从右往左遍历,找到第一个不满足单调增的值,本例中为2;
然后再次从右往左遍历,找到第一个大于2的值,本例为3;
交换以上两个元素,并将3此时所在的位置右边进行递增排序。
根据以上思路就可以完成代码,不过需要注意的是,nums已经为倒序的情况。
本文地址:https://blog.csdn.net/HizT_1999/article/details/113965442
推荐阅读
-
#leetcode刷题之路46-全排列
-
C++实现LeetCode(46.全排列)
-
天天刷leetcode——46.全排列
-
【LeetCode #46 题解】 全排列(递归回朔法、非递归实现)
-
LeetCode 由子集问题联想到的关于解决排列组合问题的位运算方法
-
【必备算法】回溯:LeetCode题 78. 子集,46. 全排列,51. N皇后,37. 解数独
-
『Leetcode 5239』循环码排列
-
【leetCode】全排列问题,不可重复+可重复
-
LeetCode 46. 全排列
-
【LeetCode】周赛纪录(八)第199场周赛20200726 重新排列字符串 灯泡开关 IV 好叶子节点对的数量 压缩字符串 II