LC31-下一个排列-next-permutation

题意

实现 next-permutation 函数。

如果不存在下一个更大的排列，则返回最小的排列（即升序排列）。

要求 O(1) 空间。

思路

思路来自 powcai提供的题解 (opens new window) 。

算法在 维基百科 (opens new window) 上有明确的描述：

1. 先找出最大的索引 k 满足 nums[k] < nums[k+1]，如果不存在，就翻转整个数组；
2. 再找出另一个最大索引 l 满足 nums[l] > nums[k]；
3. 交换 nums[l] 和 nums[k]；
4. 最后翻转 nums[k+1:]。

代码

class Solution {
    public void nextPermutation(int[] nums) {
        int size = nums.length - 1;
        // 1. 先找出最大的索引 k 满足 nums[k] < nums[k+1]，如果不存在，就翻转整个数组；
        int k = size - 1;
        while (k >= 0 && nums[k] >= nums[k + 1]) {
            k--;
        }
        if (k == -1) {
            reverse(nums, 0);
            return;
        }
        // 2. 再找出另一个最大索引 l 满足 nums[l] > nums[k]；
        int l = size;
        while (l >= 0 && nums[l] <= nums[k]) {
            l--;
        }
        // 3. 交换 nums[l] 和 nums[k]；
        swap(nums, l, k);
        // 4. 最后翻转 nums[k+1:]。
        reverse(nums, k + 1);
    }

    private static void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }

    private static void reverse(int[] nums, int l) {
        int r = nums.length - 1;
        while (l <= r) {
            swap(nums, l, r);
            l++;
            r--;
        }
    }
}