Leetcode-31:下一个排列

题目描述:
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

思路：
参考下面文章：https://www.cnblogs.com/grandyang/p/4428207.html

class Solution {
    public void nextPermutation(int[] nums) {
        //1.先找到最后一个上升的位置
        int pos = -1;
        for(int i= nums.length-1; i>0 ; i--){
            if(nums[i] > nums[i-1]){
                pos = i-1;
                break;
            }    
        }
        
        //2.如果没有这样的位置，那么说明此时序列已经是逆序的了，则把此序列逆序成最小的
        if(-1==pos){
            reverse(nums,0,nums.length-1);
            return;
        }
        
        //3.存在，则找到pos之后，最后一个比他大的位置,然后交换两者
        for(int i=nums.length-1; i>pos; i--){
            if (nums[i] > nums[pos]) {
                int tmp = nums[i];
                nums[i] = nums[pos];
                nums[pos] = tmp;
                break;
            }
        }
        reverse(nums,pos+1,nums.length-1);
        
    }
    
    public void swap(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j]=tmp;
    }
    
    // 翻转数组
    public  void reverse(int[] arr, int start, int end) {
        int l = start;
        int r = end;
        while (l < r) {
            int tmp = arr[r];
            arr[r] = arr[l];
            arr[l] = tmp;
            l++;
            r--;
        }
    }
}