C++下一個排列問題怎么解決

本文小編為大家詳細介紹“C++下一個排列問題怎么解決”，內容詳細，步驟清晰，細節處理妥當，希望這篇“C++下一個排列問題怎么解決”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。

下一個排列

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

這道題讓我們求下一個排列順序，由題目中給的例子可以看出來，如果給定數組是降序，則說明是全排列的最后一種情況，則下一個排列就是最初始情況，可以參見之前的博客 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());
    }
};

讀到這里，這篇“C++下一個排列問題怎么解決”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。