LeetCode 31. 下一个排列

31. 下一个排列

解题思路

回溯法

首先从右往左遍历数组，找到第一个满足 nums[i] < nums[i + 1] 的位置 i

• 如果没有找到，则说明当前排列已经是最大的排列，此时直接将数组反转即可得到最小的排列；
• 如果找到了位置 i，则继续从右往左遍历数组，找到第一个满足 nums[j] > nums[i] 的位置 j，交换 nums[i] 和 nums[j] 的值，然后将位置 i + 1 到数组末尾的元素进行反转，即可得到下一个排列。

参考代码

class Solution {
    public void nextPermutation(int[] nums) {
        int i;
        for(i = nums.length - 1; i >= 0; i --) {
            // 从右往左找到第一个满足 nums[i] < nums[i + 1] 的位置 i (防止越界)
            if(i + 1 < nums.length && nums[i] < nums[i + 1]) {
                for(int j = nums.length - 1; j > i; j --) {
                    if(nums[j] > nums[i]) {
                        swap(nums, i , j);
                        break;
                    }
                }
                break;
            }
        }
        // 反转候选区间
        int left = i + 1;
        int right = nums.length - 1;
        while(left < right) {
            swap(nums, left, right);
            left ++;
            right --;
        }
    }

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