下一个排列

下一个排列的定义

给定数字序列的字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列)

一123456为例,其排列依次为:

123456

123465

123546

...

654321

可以看到有这样的关系:123456 < 123465 < 123546 < ... < 654321

如何得到这样的排列顺序呢?

1. 希望下一数比当前数大，只要将后面的大树与前面的小数交换，就能得到一个更大的数。比如123456 将5和6交换就能得到一个更大的数123465

2. 还希望下一个数增加的幅度尽可能的小，以符合下一个排列与当前排列紧邻的要求，我们需要

（1）在尽可能靠右的低位进行交换，需要从后向前查找（2）将一个 尽可能小的「大数」 与前面的「小数」交换。比如 123465，下一个排列应该把 5 和 4 交换而不是把 6 和 4 交换（3）将「大数」换到前面后，需要将「大数」后面的所有数重置为升序，升序排列就是最小的排列。以 123465 为例：首先按照上一步，交换 5 和 4，得到 123564；然后需要将 5 之后的数重置为升序，得到 123546。显然 123546 比 123564 更小，123546 就是 123465 的下一个排列

算法思路

1. 从后往前查找第一个相邻升序的的元素对(i,j),满足A[i]<A[j]。此时[j,end)必然是降序的2. 在[j, end)从后往前查找第一个满足A[k] > A[i]的k,A[i],A[k],就是最小数与最大数3.将A[i]与A[k]交换4.可以断定[j,end)一点是降序的，逆置[j,end),使其升序5.如果在步骤1中找不到符合的相邻元素对，说明当前[begin,end)为一个降序顺序，直接跳到步骤4,返回最小值即可。

算法实现

class Solution { public void nextPermutation(int[] nums) { if(nums == null || nums.length == 0 || nums.length == 1){ return; } //找到nums[i]小于nums[j]的位置 int j = nums.length - 1; int i = j - 1; while(i >= 0 && nums[i] >= nums[j]){ i --; j --; } //能找到对应的位置 if(i >= 0){ int k = nums.length - 1; //从后往前找到第一个比nums[i]大的nums[k] while(k >= j && nums[k] <= nums[i]){ k --; } //交换nums[i]和nums[k] int tmp = nums[i]; nums[i] = nums[k]; nums[k] = tmp; //将nums[j-end)之间进行逆转成升序 reverseArr(nums, j, nums.length - 1); } //本身就是最大值，需要返回最小值 else{ reverseArr(nums, 0, nums.length - 1); } } //[start, end]之间对数组逆转 public void reverseArr(int[] nums, int start, int end){ if(start >= end){ return; } while(start <= end){ int tmp = nums[start]; nums[start] = nums[end]; nums[end] = tmp; start ++; end --; } } }