Leetcode31. Next Permutation

ddddLeetcode刷题

• Author：李英民 | Henry
• E-mail: li_yingmin@outlookdotcom
• $Beijing~~U~of~Posts~and~Telecom$$(BUPT~)$
• Home: https://liyingmin.wixsite.com/henry

• 快速了解我: About Me

• 转载请保留上述引用内容，谢谢配合！

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

优秀代码：

分析：

//Leetcode-31
//T(n)=O(n),S(n)=O(1)
class Solution
{
public:
    void nextPermutation(vector<int> &nums)
    {
        next_permutation(nums.begin(), nums.end());
    }
    template<typename BidiIt>
    bool next_permutation(BidiIt first, BidiIt last)
    {
// Get a reversed range to simplify reversed traversal.
        const auto rfirst = reverse_iterator<BidiIt>(last);
        const auto rlast = reverse_iterator<BidiIt>(first);
// Begin from the second last element to the first element.
        auto pivot = next(rfirst);
// Find `pivot`, which is the first element that is no less than its
// successor. `Prev` is used since `pivort` is a `reversed_iterator`.
        while (pivot != rlast && *pivot >= *prev(pivot))
            ++pivot;
// No such elemenet found, current sequence is already the largest
// permutation, then rearrange to the first permutation and return false.
        if (pivot == rlast)
            {
                reverse(rfirst, rlast);
                return false;
            }
// Scan from right to left, find the first element that is greater than
// `pivot`.
        auto change = find_if(rfirst, pivot, bind1st(less<int>(), *pivot));
        swap(*change, *pivot);
        reverse(rfirst, pivot);
        return true;
    }
};

这段代码利用了非常多C++11的特性，非常大气，但是也比较难理解，需要好好思考：

• BidiIt：bidirectional iterator，双向的迭代器

• reverse_iterator
  

  • This class reverses the direction in which a bidirectional or random-access iterator iterates through a range.
    which指代前面的direction，a bidirectional or random-access iterator iterates in the direction through a range.
  • base iterator: 这是reserve_iterator的一个伴随生成的正向迭代器，它是original iterator的一份copy，并且伴随reserve_iterator的移动而移动；注意，base iterator和reserve iterator指向不同的元素，差一位。可以通过base成员函数获得该iterator。

• reverse
  

• find_if
  
• bind1st
  
• less<int>()
  
• swap