欢迎大家参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！
链接：https://leetcode-cn.com/problems/next-permutation/
实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。
示例 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]
一些同学可能手动写排列的顺序，都没有写对，那么写程序的话思路一定是有问题的了，我这里以1234为例子，把全排列都列出来。可以参考一下规律所在：
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
如图：
以求1243为例，流程如图：
对应的C++代码如下：
class Solution {
public:
void nextPermutation(vector<int>& nums) {
for (int i = nums.size() - 1; i >= 0; i--) {
for (int j = nums.size() - 1; j > i; j--) {
if (nums[j] > nums[i]) {
swap(nums[j], nums[i]);
sort(nums.begin() + i + 1, nums.end());
return;
}
}
}
// 到这里了说明整个数组都是倒叙了，反转一下便可
reverse(nums.begin(), nums.end());
}
};class Solution {
public void nextPermutation(int[] nums) {
for (int i = nums.length - 1; i >= 0; i--) {
for (int j = nums.length - 1; j > i; j--) {
if (nums[j] > nums[i]) {
// 交换
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
// [i + 1, nums.length) 内元素升序排序
Arrays.sort(nums, i + 1, nums.length);
return;
}
}
}
Arrays.sort(nums); // 不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
}
}