31. Next Permutation


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 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

https://leetcode.com/problems/next-permutation/discuss/13867/C%2B%2B-from-Wikipedia

LeetCode All in One 题目讲解汇总(持续更新中…)

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,快快加入吧~)

知识星球 喜欢请点赞,疼爱请打赏❤️.

微信打赏

|

Venmo 打赏


—|—


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation