---
tags: LeetCode,Top 100 Liked Questions
---
# 31. Next Permutation
https://leetcode.com/problems/next-permutation/
## 題目敘述
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

The replacement must be in place and use only constant extra memory.
## Example
Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]

Example 2:

Input: nums = [3,2,1]
Output: [1,2,3]

Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]

Example 4:

Input: nums = [1]
Output: [1]

## 解題想法
### 1.Brute Force 暴力求解
把所有組合挑出來 再找到下一個組合

class Solution {
public:
    vector<vector<int>> res;
    void backtracking(vector<int> &nums, vector<int> &current, vector<bool> &used)
    {
        if (nums.size() == current.size())
        {
            res.push_back(current);
            return;
        }
        else
        {
            for (int i = 0; i < nums.size(); i++)
            {
                if (!used[i])
                {
                    used[i] = true;
                    current.push_back(nums[i]);
                    backtracking(nums, current, used);
                    used[i] = false;
                    current.pop_back();
                }
            }
        }
    }
    void nextPermutation(vector<int>& nums) {
        vector<bool> used(nums.size(),false);
        vector<int> current;
        backtracking(nums,current,used);
        sort(res.begin(),res.end());
        int now=0;
        for(int i=0;i<res.size();i++){
            if(res[i]==nums){
                now=i;
            }
        }
        if(now+1>=res.size()){
            nums=res[0];
        }
        else{
            nums=res[now+1];
        }
    }
};

時間複雜度為O(N!)(直線排列) 會在[2,1,3,1,2,0,4,1,2]測資TLE

### 2.Single Pass Approach
假設有一陣列[9, 5, 4, 3, 1]
其為往右為遞減 則無法找出next Permutation
於是知陣列往左若為遞增則無法找出next Permutation
->找出往左不為遞增的數字
且若陣列為[3, 9, 5, 4, 3, 1]
next Permutation 必為4開頭(在右邊找到最接近且>3的->從最右找到比3的)[4, 9, 5, 3, 3, 1]
然後將後段反轉 即得到next Permutation [4, 1, 3, 3, 5, 9]

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i=nums.size()-2;
        while(i>=0 && nums[i]>=nums[i+1]){
            i--;
        }
        if(i<0){
            reverse(nums.begin(),nums.end());
            return;
        }
        else{
            int k=nums.size()-1;
            while(nums[k] <= nums[i]){
                k--;
            }
            swap(nums[i],nums[k]);
            reverse(nums.begin()+i+1,nums.end());
        }
    }
};