【重点】【特例】31.下一个排列

题目

法1：找规律

class Solution {
    public void nextPermutation(int[] nums) {
        int small = -1, big = -1;
        for (int i = nums.length - 2; i >= 0; --i) {
            if (nums[i] < nums[i + 1]) {
                small = i;
                break;
            }
        }
        if (small == -1) {
            reverse(0, nums.length - 1, nums);
        } else {
            big = small + 1;
            for (int i = big; i < nums.length; ++i) {
                if (nums[i] > nums[small]) {
                    if (nums[i] <= nums[big]) { // 注意这里需要有"=", 保证small位后面的数字是降序排列
                        big = i;
                    }
                }
            }
            swap(small, big, nums);
            reverse(small + 1, nums.length - 1, nums);
        }
    }

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

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