[LeetCode] 31. Next Permutation 下一個排列

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

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

1　　2　　7　　4　　3　　1

下一個排列為：

1　　3　　1　　2　　4　　7

那么是如何得到的呢，我們通過觀察原數(shù)組可以發(fā)現(xiàn)，如果從末尾往前看，數(shù)字逐漸變大，到了2時才減小的，然后再從后往前找第一個比2大的數(shù)字，是3，那么我們交換2和3，再把此時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());
    }
};

下面這種寫法更簡潔一些，但是整體思路和上面的解法沒有什么區(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)LeetCode(31.下一個排列)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)下一個排列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論