C++怎么實(shí)現(xiàn)下一個(gè)排列

這篇文章主要介紹“C++怎么實(shí)現(xiàn)下一個(gè)排列”，在日常操作中，相信很多人在C++怎么實(shí)現(xiàn)下一個(gè)排列問題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”C++怎么實(shí)現(xiàn)下一個(gè)排列”的疑惑有所幫助！接下來，請(qǐng)跟著小編一起來學(xué)習(xí)吧！

Next Permutation 下一個(gè)排列

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

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

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

這道題讓我們求下一個(gè)排列順序，由題目中給的例子可以看出來，如果給定數(shù)組是降序，則說明是全排列的最后一種情況，則下一個(gè)排列就是最初始情況，可以參見之前的博客 Permutations。再來看下面一個(gè)例子，有如下的一個(gè)數(shù)組

1　　2　　7　　4　　3　　1

下一個(gè)排列為：

1　　3　　1　　2　　4　　7

那么是如何得到的呢，我們通過觀察原數(shù)組可以發(fā)現(xiàn)，如果從末尾往前看，數(shù)字逐漸變大，到了2時(shí)才減小的，然后再從后往前找第一個(gè)比2大的數(shù)字，是3，那么我們交換2和3，再把此時(shí)3后面的所有數(shù)字轉(zhuǎn)置一下即可，步驟如下：

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());
    }
};

下面這種寫法更簡(jiǎn)潔一些，但是整體思路和上面的解法沒有什么區(qū)別，參見代碼如下：

解法二：

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());
    }
};

到此，關(guān)于“C++怎么實(shí)現(xiàn)下一個(gè)排列”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！