**题目：**实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。 必须原地修改，只允许使用额外常数空间。 示例： 方法一：
从后往前遍历数组，找到第一个比后面小的数字a再从后往前遍历数组，找到比a大的数字b，a和b交换位置最后把a后面的数组进行排序 (如果数组整体是降序的，就直接对整个数组进行排序) class Solution { public void nextPermutation(int[] nums) { if(nums==null || nums.length<2) return; boolean flag=false; for(int i=nums.length-2;i>=0;--i){ if(nums[i]>=nums[i+1]) continue; flag=true; int j=nums.length-1; while(nums[j]<=nums[i]) j--; int temp=nums[i]; nums[i]=nums[j]; nums[j]=temp; Arrays.sort(nums,i+1,nums.length); break; } if(!flag) Arrays.sort(nums); } }方法二：暴力法 算法 在这种方法中，我们找出由给定数组的元素形成的列表的每个可能的排列，并找出比给定的排列更大的排列。 但是这个方法是一种非常天真的方法，因为它要求我们找出所有可能的排列 这需要很长时间，实施起来也很复杂。 因此，这种方法根本无法通过。 所以，我们直接采用正确的方法。 复杂度分析： 方法三：一遍扫描 算法 首先，我们观察到对于任何给定序列的降序，没有可能的下一个更大的排列。 我们交换数字 a[i-1] 和 a[j]。我们现在在索引 i-1处有正确的数字。 但目前的排列仍然不是我们正在寻找的排列。我们需要通过仅使用 a[i-1]右边的数字来形成最小的排列。 因此，我们需要放置那些按升序排列的数字，以获得最小的排列。
但是，请记住，在从右侧扫描数字时，我们只是继续递减索引直到我们找到 a[i] 和 a[i-1] 这对数。其中，a[i] > a[i-1]。因此，a[i-1]右边的所有数字都已按降序排序。此外，交换 a[i-1]和 a[j]并未改变该顺序。因此，我们只需要反转 a[i-1]之后的数字，以获得下一个最小的字典排列。
public class Solution { public void nextPermutation(int[] nums) { int i = nums.length - 2; while (i >= 0 && nums[i + 1] <= nums[i]) { i--; } if (i >= 0) { int j = nums.length - 1; while (j >= 0 && nums[j] <= nums[i]) { j--; } swap(nums, i, j); } reverse(nums, i + 1); } private void reverse(int[] nums, int start) { int i = start, j = nums.length - 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; } }