C++實(shí)現(xiàn)LeetCode(31.下一個排列)
[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)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C語言實(shí)現(xiàn)游戲VIP停車場管理系統(tǒng)
這篇文章主要介紹了C語言實(shí)現(xiàn)游戲VIP停車場管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-12-12
C語言編程數(shù)據(jù)結(jié)構(gòu)帶頭雙向循環(huán)鏈表全面詳解
這篇文章主要為大家介紹了C語言編程的數(shù)據(jù)結(jié)構(gòu)中帶頭雙向循環(huán)鏈表全面詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助祝大家多多進(jìn)步，早日升職加薪2021-10-10
這篇文章主要介紹了C++ 信號處理的相關(guān)資料，文中示例代碼非常詳細(xì)，幫助大家更好的理解和學(xué)習(xí)，感興趣的朋友可以了解下2020-07-07
C語言實(shí)現(xiàn)學(xué)生獎學(xué)金評定系統(tǒng)
這篇文章主要介紹了C語言實(shí)現(xiàn)學(xué)生獎學(xué)金評定系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
Opencv 馬賽克和毛玻璃效果與圖片融合的實(shí)現(xiàn)
這篇文章主要為大家詳細(xì)介紹了通過OpenCV實(shí)現(xiàn)馬賽克和毛玻璃濾鏡效果與圖片的融合，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11
C++實(shí)現(xiàn)飛機(jī)訂票系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)飛機(jī)訂票系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
Java?C++?算法題解leetcode669修剪二叉搜索樹示例
這篇文章主要為大家介紹了Java?C++?算法題解leetcode669修剪二叉搜索樹示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-09-09
C++空指針void是一種通用指針類型，可以指向任何類型的數(shù)據(jù)或?qū)ο?。它不關(guān)心指向的數(shù)據(jù)或?qū)ο蟮念愋?，只關(guān)心指針本身的地址，在使用void指針時，需要將其轉(zhuǎn)換為特定類型的指針，以便對其進(jìn)行操作或訪問其值，本文就給大家介紹一下C++空指針void的使用方法2023-06-06
這篇文章主要為大家詳細(xì)介紹了C語言單鏈表貪吃蛇小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-02-02
這篇文章主要介紹了C++ 遍歷某個文件夾下所有文件的方法步驟，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-02-02