# 0031. Next Permutation
###### tags: `Leetcode` `Permutation` `Medium` `FaceBook`
Link: https://leetcode.com/problems/next-permutation/

这题根本看不懂

## 翻译
找出所给定的数的一种排序，比它给定的顺序要大。例如，他如果给1，2，3，那输出就是1，3，2。如果不能再大了，就输出最小的排序。

## 思路
和[0556. Next Greater Element III](https://hackmd.io/WlpR4IShR76JdDBGWQC1Gg)一样
那题的笔记写的更好~

从后往前找，如果这一位大于或等于它的后一位，则跳过。如果这一位小于它的后一位，那么就把这一位后面所有位里面数字最小的但是又比这一位大的那个和这一位调换，再把它后面排序。如果找到开头还没找到，则全部排序。

## Code in C++

class Solution {
public:
    void(reverse(vector<int>& nums, int start_pos)){
        int i = start_pos;
        int j = nums.size()-1;
        int temp;
        while(i<j){
            temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }
    }
    void nextPermutation(vector<int>& nums) {
        int i;
        if(nums.size() != 1){
            for(i = nums.size()-2; i >= 0; i--){
                if(nums[i]<nums[i+1]){
                    break;
                }
            }
            if(i>=0){
                int j;
                for(j = nums.size()-1; j >= 0; j--){
                    if(nums[j]>nums[i]){
                        break;
                    }
                }
                swap(nums[i],nums[j]);
            }
            reverse(nums,i+1);
        }
    }
};

## Improvement
之前在找到要调换的两个数之后，我用的是sort排序，但是这道题特别的地方在于 前面已经有回圈

for(i = nums.size()-2; i >= 0; i--){
    if(nums[i]<nums[i+1]){
        break;
    }
}

检查过了i后面全部都是升序，因此可以直接用reverse函数来节省时间。

这时候我的code长这样(时间beat掉100%，但空间只beat了43.89%)

class Solution {
public:
    void(reverse(vector<int>& nums, int start_pos)){
        int i = start_pos;
        int j = nums.size()-1;
        int temp;
        while(i<j){
            temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            //swap(nums[i],nums[j]);
            i++;
            j--;
        }
    }
    void nextPermutation(vector<int>& nums) {
        int i;
        if(nums.size() != 1){
            for(i = nums.size()-2; i >= 0; i--){
                if(nums[i]<nums[i+1]){
                    break;
                }
            }
            if(i>=0){
                int min_num = INT_MAX;
                int min_pos;
                for(int j = i+1; j < nums.size();j++){
                    if(min_num>=nums[j]&&nums[j]>nums[i]){
                        min_num = nums[j];
                        min_pos = j;
                    }
                }
                swap(nums[i],nums[min_pos]);
            }
            reverse(nums,i+1);
            //sort(nums.begin()+i+1,nums.end());
        }
    }
};

为了节省空间，我将min_num min_pos两个变量的空间节省掉，也一样是因为后面是升序排列，所以才可以从后往前找，只要遇到比i位置的数大的就可以结束掉

## Result

Runtime: 4 ms, faster than **83.98%** of C++ online submissions for Next Permutation.
Memory Usage: 12 MB, less than **78.33%** of C++ online submissions for Next Permutation.

## Code in Java

class Solution {
    public void nextPermutation(int[] nums) {
        int len = nums.length;
        for (int i = len - 1; i > 0; i--){
            if (nums[i] > nums[i-1]){
                Arrays.sort(nums, i, len);
                for (int j = i; j < len; j++){
                    if (nums[j] > nums[i-1]){
                        int temp = nums[i-1];
                        nums[i-1] = nums[j];
                        nums[j] = temp;
                        return;
                    }
                }
            }
        }
        Arrays.sort(nums);
        return;
    }
}

## 思路
这题比较绕
* 在数组$x$从右向左找
* 如果存在升序$x(i-1)<x(i)$
* 确定了从$(i-1)$位开始调整
* 对$(i-1)$位之后的子数组升序排列
* 再从$i$位开始寻找第一个大于$x(i-1)$的数据，假设为$x(k)$
* 交换$x(k)$和$x(i-1)$
* return;
* 如果一直不存在升序$x(i-1)<x(i)$
* 说明数组$x$是一个降序数组
* 排列成升序
* return;