下一个排列

LeetCode 31. 下一个排列 (opens new window)

题目描述

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

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

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

示例

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

解题思路

使用回溯法能得到给定数字序列的全排列，但寻找全排列的复杂度达到O(n!)并且我们只需寻找下一个排列，所以显然不宜采用这种方法。

观察“下一个排列”的定义，回想在回溯法生成排列的过程，假设已经确定了第0个到第i-1个位置的数，现在要选择第i个位置的数字，那么可供选择的就是第i位到第n-1位的所有的数字。而输入的数组已经选择了第i个位置的元素为nums[i]，那么下一个排列要做的就是把第i个位置到第n-1个位置中最接近nums[i]且比nums[i]大的数字和nums[i]交换，再将剩余的数字按照升序排列在剩余的位置中。

现在问题在于该如何确定第i个位置，显然这个位置一定是越靠后越好，所以我们应该从后向前寻找。但同时一个连续递减的序列是其中数字所能组成的最后一个序列，所以我们应该找到从后向前首个数nums[i]满足nums[i]<=nums[i-1]，由于nums[i]后面的元素是递减的，从中从后往前找到首个大于nums[i]的数，交换两者。

剩下的就是把剩下的递减序列交换成递增的序列，如果上一步中一直找到i=-1都没有找到nums[i]<=nums[i-1]，说明整个数组都是递减的，直接交换就可以了。

public class No31_NextPermutation {
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1) return;
        int n = nums.length;

        //找到目标位置i
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1])
            i--;

        //从后往前搜索递减的部分，找到首个大于nums[i]的数，并和nums[i]交换
        if (i >= 0) {
            int k = n - 1;
            //这里可以用二分查找进行优化
            while (nums[k] <= nums[i])
                k--;
            swap(nums, i, k);
        }

        //把剩余一定是递减的部分交换成递增的
        for (int left = i + 1, right = n - 1; left < right; 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;
    }
}