LeetCode-31-下一个排列 | 李海平的博客

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

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

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

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。

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

字典序

参照百度百科中字典序的概念：

在数学中，字典或词典顺序（也称为词汇顺序，字典顺序，字母顺序或词典顺序）是基于字母顺序排列的单词按字母顺序排列的方法。这种泛化主要在于定义有序完全有序集合（通常称为字母表）的元素的序列（通常称为计算机科学中的单词）的总顺序。

对于数字1、2、3......n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列 12354和12345，排列12345在前，排列12354在后。按照这样的规定，5个数字的所有的排列中最前面的是12345，最后面的是 54321。

以1、2、3为例，其构成的所有排列如下：

123->132->213->231->312->321

简单来讲，字典序就是保持左边不变（变得最慢），右边依次从正序到逆序的排列过程。

下一个排列

字典序的百度百科也有关于下一个排列的求解方法：

设P是1～n的一个全排列:p=p1p2......pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn
1）从排列的右端开始，找出第一个比右边数字小的数字的序号j（j从左端开始计算），即 j=max{i|pi<pi+1}
2）在pj的右边的数字中，找出所有比pj大的数中最小的数字pk，即 k=max{i|pi>pj}（右边的数从右至左是递增的，因此k是所有大于pj的数字中序号最大者）
3）对换pj，pk
4）再将pj+1......pk-1pkpk+1......pn倒转得到排列p'=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1，这就是排列p的下一个排列。

所以不考虑边界情况，求下一个排列的过程可以分为四步：

从右往左找到第一个比右边数字小的序号i
再次从右往左找到第一个比p[i]大的序号j
交换p[i]和p[j]
将i右边的数字全部倒转

具体的实现代码如下：

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
const nextPermutation1 = function(nums) {
    if (nums.length < 2) {
        return;
    }
    let [i, j] = [nums.length - 1, nums.length - 1];
    // 从右往左找到第一个比右边数字小的序号i
    while (i >= 0) {
        i --;
        if (nums[i] < nums[i + 1]) {
            break;
        }
    }
    // 没有找到，证明当前已是最大序列，全部倒序，然后返回
    if (i < 0) {
        for (let k = 0; k < nums.length/2; k ++) {
            [nums[k], nums[nums.length - 1 - k]] = [nums[nums.length - 1 - k], nums[k]]
        }
        return;
    }
    // 从右往左找到第一个比p[i]大的序号j
    while (j > i) {
        if (nums[j] > nums[i]) {
            break;
        }
        j --;
    }
    // 交换p[i]和p[j]
    [nums[i], nums[j]] = [nums[j], nums[i]];
    // 将i右边的数字全部倒转
    for (let k = i + 1; k < (nums.length - i - 1)/2 + i + 1; k ++) {
        [nums[k], nums[nums.length - k + i]] = [nums[nums.length - k + i], nums[k]]
    }
};

测试：

let start = new Date();
const test = nextPermutation1;
let nums = [1, 2, 3];
test(nums);
console.log(nums); // [ 1, 3, 2 ]

nums = [3, 2, 1];
test(nums);
console.log(nums); // [ 1, 2, 3 ]

nums = [1, 1, 5];
test(nums);
console.log(nums); // [ 1, 5, 1 ]

nums = [1, 3, 2];
test(nums);
console.log(nums); // [ 2, 1, 3 ]
console.log(new Date().getTime() - start.getTime()); // 8

时间复杂度： 多次遍历，但是没有嵌套遍历，时间复杂度为$O(n)$
空间复杂度： 常数级的额外空间，空间复杂度为$O(1)$

本文由 李海平 创作，采用知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 3,2019