題目描述

實現(xiàn)獲取下一個排列的函數(shù)，算法需要將給定數(shù)字序列重新排列成字典序中下一個更大的排列。
如果不存在下一個更大的排列，則將數(shù)字重新排列成最小的排列（即升序排列）。
必須原地修改，只允許使用額外常數(shù)空間。
以下是一些例子，輸入位于左側(cè)列，其相應(yīng)輸出位于右側(cè)列。
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.從右往左找到第一個(左<右)的左坐標(biāo)記為i;
2.將nums[i]與右側(cè)最后一個大于nums[i]的數(shù)進行交換
3.將右側(cè)整體進行逆序.

用到的stl

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