標簽： C++ 算法 LeetCode 數(shù)組

每日算法——leetcode系列

問題 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) {
        
    }
};

翻譯

下一個排列

難度系數(shù)：中等
實現(xiàn)下一個排列，此排列是按字典的順序的來重新編排數(shù)字得到的下一個大的數(shù)字排列。
如果不能重排成下一個大的數(shù)字排列，那必須按最小可能的順序來重排（例如：按升序排列）
重排必須在原地，不準分配額外的內(nèi)存。

思路

此題的意思就是按字典的順序從當前的順序找下一個順序的排列組合，什么是字典順序，基本規(guī)則就是字母表從小到大， 如果一些單詞是abcd組成，字母表順序是abcd->abdc->acbd->acdb->adbc->adcb->...依次往下。

分析規(guī)律：

• abcd->abdc 最后兩個交換
• abdc->acbd 先bc交換，再db交換
• acbd->acdb bd交換
• acdb->adbc 先cd交換， 再cb交換
• adbc->adcb 最后兩個交換
  規(guī)律有點難發(fā)現(xiàn)，其實在交換中我們下意識運用了規(guī)律(我是偷了別個的思想)。
  以abcd->abdc為例

1. 從右到左看，先找到第一個打破升序規(guī)律的字母c
2. 再從頭來從右到左，找出c右邊比c大的字母d（其實字典順序他肯定在c右邊），并把c右邊的字母作為一個分區(qū)段
3. 交換c,d
4. 分區(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;
            }
        }
        // 沒找到打破升序規(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());
    }
};