题目描述：
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3→ 1,3,2
3,2,1→ 1,2,3
1,1,5→ 1,5,1
题目难度：中等
分析：
题目的下一个排列可以理解为：把数组看成一个int值，找出下一个比当前更大的int值，当然元素不能变，只能交换。所以只有降序排列的数组是没有下一个排列的。那么我们只要从后往前，找到第一个后元素大于前元素的位置，记录前元素为index，说明此数组不是降序排序，找到之后再从后往前遍历，找到第一个大于index索引的值，并且交换即可，这里只需要遍历到index后一位。
代码如下：
class Solution { public void nextPermutation(int[] nums) { // 如果数组的长度等于1，就不需要排列了，直接返回 int l = nums.length; if (l == 1) { return; } // 定义一个索引，并且从后往前找到第一个nums[i] > nums[i - 1]的位置 int index = -1; for (int i = l - 1; i > 0; i--) { if (nums[i] > nums[i - 1]) { index = i - 1; break; } } // 如果没有找到，说明数组是降序排列，没有下一个排列，直接升序排序即可 if (index == -1) { Arrays.sort(nums); return; } // 继续从后向前遍历，找到第一个比index索引的值大的值 for (int i = l - 1; i > index; i--) { if (nums[i] > nums[index]) { // 交换位置 nums[index] 和 nums[i]交换 swap(nums, index, i); break; } } // 对index后面的元素首尾交换，因为这个地方肯定是倒序排序的 int i = index + 1, j = l - 1; while (i < j) { swap(nums, i, j); i++; j--; } } // 用来交换数组元素的方法 private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }
这里借用官方的动图来让大家理解更深刻：
总结：
时间复杂度为O ( n ) ，需要遍历数组，最差需要遍历两次全数组。
