leetcode题目31. 下一个排列（java）

题目描述

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。必须原地修改，只允许使用额外常数空间。

示例

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

代码

public void nextPermutation(int[] nums) {
    int i = nums.length - 1;
    while (i > 0) {
        if (nums[i - 1] < nums[i]) {
            // 从后往前遍历，找到第一个递减的数字，位置为i
            break;
        }
        i = i - 1;
    }
    i = i - 1;
    if (i >= 0) {
        int j = i+1;
        // 如果i =  0，说明整个序列是递增的，无需进行下面操作
        for (; j < nums.length; j++) {
            if (nums[j] <= nums[i]) {
                // 找到i之后比num[i]大的最小的一个数字。因为i后的数字是递减的，所以很好找到
                // 交换者两个数字
                break;
            }
        }
        swap(nums, i, j - 1);
    }
    // 将i之后的数字进行反转，即
    reverse(nums, i + 1, nums.length - 1);
}

public void reverse(int[] nums, int i, int j){
    while (i < j) {
        swap(nums, i, j);
        i++;
        j--;
    }
}

public void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}