31. Next Permutation

置顶

Created At : 2021-04-07 23:57

Count:792 Views 👀 :

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

For example, the next permutation of arr = [1,2,3] is [1,3,2].
Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

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

Example 1:

**Input:** nums = [1,2,3]
**Output:** [1,3,2]

Example 2:

**Input:** nums = [3,2,1]
**Output:** [1,2,3]

Example 3:

**Input:** nums = [1,1,5]
**Output:** [1,5,1]

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 100

这道题让我们求下一个排列顺序，由题目中给的例子可以看出来，如果给定数组是降序，则说明是全排列的最后一种情况，则下一个排列就是最初始情况，可以参见之前的博客 Permutations。再来看下面一个例子，有如下的一个数组

1 2 7 4 3 1

下一个排列为：

1 3 1 2 4 7

那么是如何得到的呢，我们通过观察原数组可以发现，如果从末尾往前看，数字逐渐变大，到了2时才减小的，然后再从后往前找第一个比2大的数字，是3，那么我们交换2和3，再把此时3后面的所有数字转置一下即可，步骤如下：

1 2 7 4 3 1

1 3 7 4 2 1

1 3 1 2 4 7

解法一：

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        int i, j, n = num.size();
        for (i = n - 2; i >= 0; --i) {
            if (num[i + 1] > num[i]) {
                for (j = n - 1; j > i; --j) {
                    if (num[j] > num[i]) break;
                }
                swap(num[i], num[j]);
                reverse(num.begin() + i + 1, num.end());
                return;
            }
        }
        reverse(num.begin(), num.end());
    }
};

下面这种写法更简洁一些，但是整体思路和上面的解法没有什么区别，参见代码如下：

解法二：

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size(), i = n - 2, j = n - 1;
        while (i >= 0 && nums[i] >= nums[i + 1]) --i;
        if (i >= 0) {
            while (nums[j] <= nums[i]) --j;
            swap(nums[i], nums[j]);
        }
        reverse(nums.begin() + i + 1, nums.end());
    }
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/31

类似题目：

Permutations II

Permutations

Permutation Sequence

Palindrome Permutation II

Palindrome Permutation

Minimum Adjacent Swaps to Reach the Kth Smallest Number

参考资料：

https://leetcode.com/problems/next-permutation/

https://leetcode.com/problems/next-permutation/discuss/13921/1-4-11-lines-C%2B%2B