LeetCode31.下一个排列-蟒蛇

31.NextPermutation题目实现了获取下一个排列的功能。该算法需要将给定的数字序列重新排列为字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列为最小的排列（即升序）。必须就地修改，只允许额外的常量空间。下面是一些示例，左栏中有输入，右栏中有相应的输出。1,2,3→1,3,23,2,1→1,2,31,1,5→1,5,1解题思路：迭代先理解题意，需求在问题【将给定的数列按照字典顺序重新排列成下一个更大的排列。如果不存在，重新排列数字，称其为最小排列（即升序排列）】这里，可能直接从正文中看出来，也不太难理解是什么意思，所以结合例子，先看1,2,3→1,3,21,1,5→1,5,1在这里，你可以理解为将数字123变为下一个更大的数字132。同样适用于115.而下面的例子表示没有更大的排列：3,2,1→1,2,3321已经是最大的，然后将其排列成最小的排列（升序），得到结果123。在其实从上面的例子中，或多或少可以看出，这里的查找其实是从后面开始的。当找到两个相邻的数字从小到大的时候，就在这里交换，这样就可以得到更大的排列。其实这里还有一部分内容，在标题中比较难看出。题目中“next”的概念其实就是找变化前后的排列，增加的越少越好。例如下面的例子：1,2,3,4,5→1,2,3,5,41,2,3,5,4→1,2,4,3,5第一个例子，根据上面观察到替换4和5会导致更大的排列，12354。下面例子中的12354，导致排列为12435，这里交换了3和4。其实这里交换的数是尽可能小的大数和前面的小数，所以交换的不是3和5，交换后的所有数字都需要按升序重新设置。得到的结果是12435，不是12453，这是简单分析题意。下面看看算法是如何实现的：首先需要从后往前按升序找出前两个相邻元素的位置(i,j)，满足A[i]None:"""不返回任何东西，就地修改nums。"""iflen(nums)<2:returnn=len(nums)#从数组的右边向前面遍历，找到相邻的升序元素i=n-2j=n-1whilei>0andnums[i]>=nums[j]:i-=1j-=1#这里有一种情况，就是循环结束后，i为0，索引0位置的数最大#那么这就说明排列是最大的排列，倒序为升序ifi==0andnums[i]==max(nums):nums.reverse()else:#当查找相邻的升序元素时#找到一个比nums[i]大但尽可能小的数kotherelementsfrombacktofrontagain=n-1whilenums[i]>=nums[k]:k-=1#交换两个元素nums[i],nums[k]=nums[k],nums[i]#现在j到下一个元素是降序的，这里应该是升序length=n-j+1forxinrange(length//2):nums[j+x],nums[n-1-x]=nums[n-1-x],nums[j+x]执行结果以上是分析《31. 下一个排列》问题及具体实现算法的主要内容。欢迎关注微信公众号《书所集录》