標(biāo)簽： C++ 算法 LeetCode 數(shù)組
每日算法——leetcode系列
問(wèn)題 Next Permutation
Difficulty: Medium
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, do not allocate 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
class Solution {
public:
void nextPermutation(vector<int>& nums) {
}
};
翻譯
下一個(gè)排列
難度系數(shù)：中等
實(shí)現(xiàn)下一個(gè)排列沸停，此排列是按字典的順序的來(lái)重新編排數(shù)字得到的下一個(gè)大的數(shù)字排列龄恋。
如果不能重排成下一個(gè)大的數(shù)字排列督弓，那必須按最小可能的順序來(lái)重排（例如：按升序排列）
重排必須在原地，不準(zhǔn)分配額外的內(nèi)存曙寡。
思路
此題的意思就是按字典的順序從當(dāng)前的順序找下一個(gè)順序的排列組合，什么是字典順序，基本規(guī)則就是字母表從小到大救斑， 如果一些單詞是abcd組成，字母表順序是abcd->abdc->acbd->acdb->adbc->adcb->...依次往下哗总。
分析規(guī)律：
- abcd->abdc 最后兩個(gè)交換
- abdc->acbd 先bc交換几颜，再db交換
- acbd->acdb bd交換
- acdb->adbc 先cd交換， 再cb交換
- adbc->adcb 最后兩個(gè)交換
規(guī)律有點(diǎn)難發(fā)現(xiàn)讯屈，其實(shí)在交換中我們下意識(shí)運(yùn)用了規(guī)律(我是偷了別個(gè)的思想)蛋哭。
以abcd->abdc為例
- 從右到左看，先找到第一個(gè)打破升序規(guī)律的字母c
- 再?gòu)念^來(lái)從右到左涮母，找出c右邊比c大的字母d（其實(shí)字典順序他肯定在c右邊）谆趾，并把c右邊的字母作為一個(gè)分區(qū)段
- 交換c,d
- 分區(qū)段的字母再按升序排列，這里由于就剩下c叛本，升序排序后還是剩下c
代碼
class Solution {
public:
void nextPermutation(vector<int>& nums) {
size_t len = nums.size();
if (len == 1 || len == 0){
return;
}
int firstBreakNum = -1;
size_t firstBreakIndex = -1;
for (size_t i = len ;i > 1; --i){
if (nums[i-1] > nums[i-2]){
firstBreakNum = nums[i-2];
firstBreakIndex = i - 2;
break;
}
}
// 沒(méi)找到打破升序規(guī)律的沪蓬，那就全部升序排列
if (firstBreakNum == -1){
reverse(nums.begin(), nums.end());
return;
}
for (size_t i = len; i > 1; --i){
if (nums[i-1] > firstBreakNum){
swap(nums[i-1], nums[firstBreakIndex]);
break;
}
}
auto iter = nums.begin();
for (size_t i = 0; i < firstBreakIndex + 1; ++i){
iter++;
}
reverse(iter, nums.end());
}
};
