31-下一个排列

Leetcode题解
  1. 31、下一个排列
    1. 题目：
    2. 题解：

31、下一个排列

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

题目：

U652nI.png

题解：

此题乍一看非常的难理解，通过评论区翻译后得知，题目输入提供了一个数组，每个数组元素都是一个0-9的数字，这一个数组组成的数字序列可以一个数值。题目的要求就是调整数字序列来让这个数值是下一个更大的数值；如果这个数字序列是降序排序的，很明显已经是最大的数值了，就要求把序列改成最小的序列（很明显就是reverse即可）

由数字全降序为最大数值我们可知，一旦这个数字序列不是降序，必然有下一个序列组成更大的数值。那么就可以用指针A从右向左遍历直到遍历到非降序的事件发生，也就是nums[A] < nums[A+1]。此时，再从A右侧的数字序列中选择一个“nums[A]下一个更大的数值”与nums[A]进行swap，然后对右侧的降序序列reverse为升序即可。

U65Gp4.png

全降序直接reverse；非全降序找到右向左遍历的”升序值”与右侧较大于“升序值”的数swap后再reverse”升序值”右部分序列即是”更大的数值”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i = 0;
        int n = nums.size();
        for (i = n-2; i >= 0; i-- ) {
            if (nums[i+1] > nums[i]) {
                break;
            }
        }
        if (i >= 0) {
            int j;
            for (j = n-1; j >= i+1; j--) {
                if (nums[j] > nums[i]) {
                    swap(nums[j], nums[i]);
                    break;
                }
            }
            int l = i+1, r = n-1;
            while (l < r) {
                swap(nums[l], nums[r]);
                l++;
                r--;
            }
            return;
           
        } else {
            int l = 0, r = n-1;
            while (l < r) {
                swap(nums[l], nums[r]);
                l++;
                r--;
            }
            return;
        }
    }
};

当前网速较慢或者你使用的浏览器不支持博客特定功能，请尝试刷新或换用Chrome、Firefox等现代浏览器