题目链接
题目简介
实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。
示例 1：
输入：nums = [1,2,3] 输出：[1,3,2]
示例 2：
输入：nums = [3,2,1] 输出：[1,2,3]
示例 3：
输入：nums = [1,1,5] 输出：[1,5,1]
示例 4：
输入：nums = [1] 输出：[1]
题目解析
- 我们可以将该问题形式化地描述为：给定若干个数字，将其组合为一个整数。如何将这些数字重新排列，以得到下一个更大的整数。如 123 下一个更大的数为 132。如果没有更大的整数，则输出最小的整数。
- 我们希望下一个数字比 当前的数字大，这样才能满足 下一个排列 的定义。因此只需要 将后面的【大数】与前面的【小数】交换，就能得到一个更大的数。比如：
123456，将5和6进行交换即可，就能得到一个更大的数字123465 - 我们希望下一个数字增幅尽量的小，这样才满足下一个排列与当前排列紧邻的要求，为了满足这个要求，我们需要
- 在 尽可能靠右的低位 进行交换，需要 从后往前 扫描
- 将一个 尽可能小的【大数】 与 前面的【小数】 交换。比如
123465，下一个排列应该把5和4交换而不是把6和4交换 - 将【大数】换到前面后，需要将大数后面的所有数 重新进行排序，保证升序序列就是最小的排列。
- 以
123465为例，我们在将5和4交换后，得到123564，然后需要将5之后的数重新进行排序，也就是123546
题目代码
public void nextPermutation(int[] nums) { if(nums.length == 0 || nums.length == 1){ return; } int i = nums.length - 2; while(i >= 0 && nums[i] >= nums[i+1]){ i--; } if(i >= 0){ int j = nums.length - 1; while(j >= 0 && nums[j] <= nums[i]){ j--; } swap(nums, i, j); } resver(nums, i + 1, nums.length - 1); } public void swap(int[] nums, int i, int j){ int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } public void resver(int[] nums, int start, int end){ while(start <= end){ swap(nums, start, end); start++; end--; } }
