31.下一个排列

题目描述

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

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

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

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。

示例一：

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

思路

1.其实本题中的下一个排列就是比当前数大的下一个数。
2.我们首先应该找到那对应该被交换的数字。
3.左边应该被交换的数字符合nums[i]<nums[i-1]的特征；右边应该被交换的数是刚好大于左边数字的最小数字，即j in (i+1,nums.length-1) && min(i+1,nums.length-1) && nums[j]>nums[i]。
4.我们交换数据后，将左边数字的右边进行从小到大排序即可。
例如：

1587624310
1.找到 2 为左边应该被交换位置的数
2.找到 3 为右边应该被交换位置的数
3.交换 2 和 3 的位置--->1587634210
4.升序排序 3 右边的数字  ---->1587630124

Java代码实现

  public void nextPermutation(int[] nums) {
        int i = nums.length-2;
        //寻找左边的数
        while(i>=0 && nums[i]>=nums[i+1]){
            i--;
        }
        //寻找右边的数
        if(i>=0){
            int j = nums.length-1;
            while(nums[j]<=nums[i]){
                j--;
            }
            swap(nums,i,j);
        }
        //因为右边的数交换完成后是降序的，所以直接翻转即可
        reverseNums(nums,i+1,nums.length-1);
    }

    private void reverseNums(int[] nums,int left,int right){
        while(left<right){
            swap(nums,left++,right--);
        }
    }

    private void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

Golang代码实现

func nextPermutation(nums []int)  {
    i := 0
    for i =len(nums)-2 ; i>=0 ; i--{
        if nums[i] < nums[i+1] {
            for j := len(nums)-1; j>i;j--{
                if nums[j] > nums[i] {
                    swap(nums,i,j)
                    break
                }
            }
            break
        }
    }
    reverseNums(nums,i+1,len(nums)-1)
}

func swap(nums []int,left int,right int){
    temp := nums[left]
    nums[left] = nums[right]
    nums[right] = temp
}

func reverseNums(nums []int,left int,right int){
    for left <= right {
        swap(nums,left,right)
        left++
        right--
    }
}