题目描述

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

知识点

字典序排列的过程

AC代码

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int j;
        int len = nums.size();
        int i = len - 1;
        if (len == 1) {
            return;
        }
        for (; i > 0; --i) {
            if (nums[i - 1] < nums[i]) {
                break;
            }
        }
        if (i == 0) {
            swapitend(nums, i, len - 1);
            return;
        }
        j = i;
        --i;
        while (j < len && nums[i] < nums[j]) {
            ++j;
        }
        swap(nums, i, j - 1);
        swapitend(nums, i + 1, len - 1);
    }

    void swap(vector<int> &nums, int i, int j){
        nums[i] = nums[i] + nums[j];
        nums[j] = nums[i] - nums[j];
        nums[i] = nums[i] - nums[j];
    }

    void swapitend(vector<int> &nums, int i, int end){
        while (i < end) {
            swap(nums, i, end);
            ++i;
            --end;
        }
    }
};

真的写的自己都觉得很垃圾.边界条件也试了好多次.

字典序的核心思路

1.从右往左找到第一个(左<右)的左坐标记为i;
2.将nums[i]与右侧最后一个大于nums[i]的数进行交换
3.将右侧整体进行逆序.

用到的stl

reverse(nums.begin() + pos, nums.end());
swap(nums[i], nums[j])