solution.md

# 下一个排列

<p>实现获取 <strong>下一个排列</strong> 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。</p><p>如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。</p><p>必须<strong><a href="https://baike.baidu.com/item/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95" target="_blank"> 原地 </a></strong>修改，只允许使用额外常数空间。</p><p> </p><p><strong>示例 1：</strong></p><pre><strong>输入：</strong>nums = [1,2,3]<strong><br />输出：</strong>[1,3,2]</pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>nums = [3,2,1]<strong><br />输出：</strong>[1,2,3]</pre><p><strong>示例 3：</strong></p><pre><strong>输入：</strong>nums = [1,1,5]<strong><br />输出：</strong>[1,5,1]</pre><p><strong>示例 4：</strong></p><pre><strong>输入：</strong>nums = [1]<strong><br />输出：</strong>[1]</pre><p> </p><p><strong>提示：</strong></p><ul>	<li><code>1 <= nums.length <= 100</code></li>	<li><code>0 <= nums[i] <= 100</code></li></ul>
<p>以下<span style="color:red">错误</span>的选项是？</p>


## 答案

```c
class Solution
{
public:
    void nextPermutation(vector<int> &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<int> &nums, int i, int j)
    {
        int temp = nums.at(j);
        nums.at(j) = nums.at(i);
        nums.at(i) = temp;
    }
    void reverse(vector<int> &nums, int i, int j)
    {
        while (i < j)
        {
            swap(nums, i, j);
            i++;
            j--;
        }
    }
};
```
## 选项


### A

```c
class Solution
{
public:
	void nextPermutation(vector<int> &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

```c
class Solution
{
public:
    void nextPermutation(vector<int> &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

```c
void reverse(vector<int> &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<int> 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<int> &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;
        }
    }
};

```