leetcode 題解 || Next Permutation 問題

problem：

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

 

Hide Tags Array

 

 

 

 

題意：

給一個序列，找出下一個緊挨著的序列。比如 1 ，2， 3 的下一個序列是 1， 3 ，2 ；

注意： 3 ，2 ，1 的下一個序列 是它的反轉： 1 ，2 ，3

 

 

thinking：

（1）這是排列組合算法的一種實現方法，難點在於找到緊挨著該序列的 下一個序列

（2）這裡采用了 STL ：

【STL】next_permutation的原理和使用

精華在於，從序列的後端逆序比較，比如 1 ，2， 3 的下一個序列是 1， 3 ，2 ，這樣只需交換 2,3即可。 對於序列1, 2, 5, 4, 3：逆序尋找到2 ， 5，發現這兩個元素是順序的，則從尾部逆序尋找一個比2 大的數，這裡是3，和2 交換位置，變成1 ，3 ，5 ，4 ，2 最後再，反轉5， 4， 2 即可得到下一個序列： 1 ，3 ，2， 4， 5

 

code：

 

class Solution {
public:
    void nextPermutation(vector &num) {
        vector::iterator first = num.begin();
        vector::iterator last = num.end();

        vector::iterator tmp = first;
        if(++tmp == last)
            return;
        vector::iterator i  = last;
        i--;
        for(;;) {
            vector::iterator ii = i;
            --i;
            /*
            *從尾部逆序比較兩個相鄰的元素，如果尾部m個元素一直是逆序的，說明尾部已經足夠大
            *這時需要不斷往頭部移動，直到找到一對順序的相鄰元素i、ii，再從尾部找一個比i還小的元素j
            *先交換i 和  j元素，再將ii~last之間的元素反轉
            */
            if(*i < *ii) {
                vector::iterator j = last;
                while(!(*i < *--j));

                iter_swap(i, j);//與swap（）稍有不同，iter_swap（）的參數是對迭代器的引用
                reverse(ii, last);
                return;
            }

            if(i == first) {
                reverse(first, last);  //全逆向，即為最小字典序列，如cba變為abc
                return;
            }
        }//for

    }
};