leetcode第31题，要求给定一组数字，输出字典序下下一个全排列，要求原地修改。
首先，要求原地修改，就不要想着先生成在去查找这个办法了。其实这个方法比较难想出来，主要是找按字典序排列的相邻的全排列之间有什么规律。
从最后一位向前搜索，如果一直处于递增状态，说明这一段全排列没法动，因为这一个子段已经处于字典序的最大值了，无论怎么换，都不可能增大这一段的字典序。直到发现搜索到某个位置，递增被打断，说明这个地方还没有满足全排列的最大值，可以做手脚了。于是我们从这个截断点反向搜索一个只比他小一点的数，交换其位置。最后一步，由于这个子段已经处于全排的最大字典序，因此就如同加法进位一样，自动回转到字典序最小值，也就是逆序一下就可以了。
class Solution(object): def nextPermutation(self, nums): """ :type nums: List[int] :rtype: void Do not return anything, modify nums in-place instead. """ def swap(nums,i1,i2): tmp = nums[i1] nums[i1] = nums[i2] nums[i2] = tmp def reverse(nums, start, end): while start < end: swap(nums, start, end) start += 1 end -= 1 n = len(nums) i = n-2 while i >= 0 and nums[i+1] <= nums[i]: i -= 1 if i >= 0: j = n-1 while j >= 0 and nums[j] <= nums[i]: j -= 1 swap(nums, i, j) reverse(nums, i+1, n-1)新闻热点
疑难解答
