下一个排列（简答实现）

题目

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。必须原地修改，只允许使用额外常数空间。

例子： 以下是一些例子，输入位于左侧列，其相应输出位于右侧列。 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

思路

1、该题可以理解为给定若干个数字，将其组合为一个整数。如何将这些数字重新排列，以得到下一个更大的整数；（比如1，2，3得到数字123，通过重新排列，得到下一个更大的数132） 2、要找到更大的数，我们只需要将后面比较大的数与前面比较小的数进行交换；为了使得增幅是最小的，我们需要在尽可能靠右的低位中找到尽可能小的大数和前面的小数进行交换，并且对大数（交换之后的位置）之后重置为升序。 3、编程思路：

从后往前寻找第一个相邻升序对(j - 1,j)，即nums[j - 1]<nums[j] ；再从后往前寻找第一个大于nums[i]的数（即尽可能小的大数），尽可能小的大数和前面的小数（即nums[j - 1]）进行交换；然后将大数后面的重置为升序。（因为[j，end]为降序所以只要递归前后交换即可）

实现

public void nextPermutation(int[] nums) { if(nums.length <= 1) return; int j = nums.length - 1; int i = 0; //用于记录尽可能靠后的最小数的位置（j - 1） boolean flag = false; //true表示存在下一个更大的排列，false表示不存在 //从后往前寻找第一个相邻升序对 while(j > 0){ if(nums[j - 1] < nums[j]){ i = j - 1; flag = true; break; } j --; } //从后往前寻找尽可能小的大数，并与之前的小数交换位置 if(flag){ int k = nums.length - 1; while(k > 0){ if(nums[k] > nums[i]){ int temp = nums[k]; nums[k] = nums[i]; nums[i] = temp; break; } k --; } } //将大数后面的部分倒序。 int l = nums.length - 1; while(j < l){ int t = nums[j]; nums[j] = nums[l]; nums[l] = t; j ++; l --; } }