C++實(shí)現(xiàn)LeetCode(31.下一個(gè)排列)

更新時(shí)間：2021年07月14日 10:25:17 作者：Grandyang

這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(31.下一個(gè)排列),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[LeetCode] 31. 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　　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.下一個(gè)排列)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)下一個(gè)排列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: