# 下一个排列
实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。
示例 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]
提示：
1 <= nums.length <= 1000 <= nums[i] <= 100
以下错误的选项是？
## aop
### before
```cpp
```
### after
```cpp
```
## 答案
```cpp
class Solution
{
public:
void nextPermutation(vector &nums)
{
if (nums.size() <= 1)
return;
int i, j;
for (i = nums.size() - 2; i >= 0; i--)
{
if (nums.at(i) < nums.at(i + 1))
break;
}
if (i < 0)
reverse(nums, 0, nums.size() - 1);
else
{
for (j = nums.size() - 1; j > i; j--)
{
if (nums.at(j) > nums.at(i))
break;
}
swap(nums, i, j);
reverse(nums, i, nums.size() - 1);
}
}
void swap(vector &nums, int i, int j)
{
int temp = nums.at(j);
nums.at(j) = nums.at(i);
nums.at(i) = temp;
}
void reverse(vector &nums, int i, int j)
{
while (i < j)
{
swap(nums, i, j);
i++;
j--;
}
}
};
```
## 选项
### A
```cpp
class Solution
{
public:
void nextPermutation(vector &nums)
{
if (nums.size() < 2)
{
return;
}
int i = nums.size() - 2;
while (i >= 0 && nums[i] >= nums[i + 1])
{
i--;
}
if (i >= 0)
{
int j = nums.size() - 1;
while (j >= 0 && nums[j] >= nums[i])
{
j--;
}
swap(nums.begin() + i, nums.begin() + j);
}
reverse(nums.begin() + i + 1, nums.end());
}
};
```
### B
```cpp
class Solution
{
public:
void nextPermutation(vector &num)
{
int index = num.size() - 1;
while (num[index - 1] >= num[index])
{
index--;
}
if (index == 0)
{
sort(num.begin(), num.end());
return;
}
for (int i = num.size() - 1; i >= index; i--)
{
if (num[i] > num[index - 1])
{
swap(num[i], num[index - 1]);
break;
}
}
sort(num.begin() + index, num.end());
return;
}
};
```
### C
```cpp
void reverse(vector &nums, int begin, int end)
{
while (begin < end)
{
int temp = nums[begin];
nums[begin] = nums[end];
nums[end] = temp;
begin++;
end--;
}
return;
}
int minIndex(vector nums, int begin, int end, int i)
{
int min = nums[begin];
int x = i;
for (int j = begin; j <= end; j++)
{
if (min >= nums[j] && nums[j] > nums[i])
{
min = nums[j];
x = j;
}
}
return x;
}
class Solution
{
public:
void nextPermutation(vector &nums)
{
if (nums.size() == 0 || nums.size() == 1)
{
return;
}
int size = nums.size();
int i = 0;
for (i = size - 2; i >= 0; i--)
{
if (nums[i] < nums[i + 1])
{
break;
}
}
if (i == -1)
{
reverse(nums, 0, size - 1);
return;
}
else
{
int min = minIndex(nums, i + 1, size - 1, i);
int temp = nums[i];
nums[i] = nums[min];
nums[min] = temp;
sort(nums.begin() + i + 1, nums.end());
return;
}
}
};
```