LeetCode算法笔记--下一个排列

算法题热题HOT100

字数统计: 388阅读时长: 1 min

 2020/12/05   Share

LeetCode算法笔记–Day36

31. Next Permutation

题目：

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

My Answer：

方法一：扫描

e56a66ed318d1761cd8c8f9d1521f82a30c71ecc84f551912b90d8fe254c8f3d-image.png

1.从后向前查找第一个相邻升序的元素对 (i,j)，满足 A[i] < A[j]。此时 [j,end) 必然是降序.
2.在 [j,end) 从后向前查找第一个满足 A[i] < A[k] 的 k。A[i]、A[k] 分别就是上文所说的「小数」、「大数」.
3.将 A[i] 与 A[k] 交换.
4.可以断定这时 [j,end) 必然是降序，逆置 [j,end)，使其升序.
5.如果在步骤 1 找不到符合的相邻元素对，说明当前 [begin,end) 为一个降序顺序，则直接跳到步骤 4

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function(nums) {
    let i=-1,j=-1;
    // 从后向前获取第一组相邻升序的坐标
    for(let _p = nums.length-1;_p>=0;_p--){
        if(nums[_p]>nums[_p-1]){
            i = _p-1;
            j = _p;
            break;
        }
    }
    // 最大排列则返回最小排列
    if(i<0) return nums.reverse();
    // 从后向前获取第一个大于nums[i]的值与之交换
    for(let _p = nums.length-1;_p>=j;_p--){
        if(nums[_p]>nums[i]){
            nums[_p] = [nums[i],nums[i]=nums[_p]][0];
            break;
        }
    }
    // j之后的降序变升序
    return nums.slice(0,j).concat(nums.slice(j).reverse())

};

Next Post

LeetCode算法笔记--搜索旋转排序数组
Previous Post

LeetCode算法笔记--合并两个有序链表

CATALOG

1. LeetCode算法笔记–Day36
2. 31. Next Permutation
1. 2.1. 题目：
2. 2.2. My Answer：
  1. 2.2.1. 方法一：扫描

