Leetcode之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, 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

1,2,6,4->1,4,2,6

问题来源：Next Permutation (详细地址：https://leetcode.com/problems/next-permutation/description/)

思路分析:

先把题目解释一下，题目说的是要找到该序列按字典顺序的下一个序列，如果没有找到的话，那我们就按照顺序递增的顺序排列起来。其实，我们可以分为一下几步完成：

1.我们必须首先要找到需要交换的数字，这个简单，直接从右往左找，找到第一个比它右边大的数字，直接跳出来就找到了；

2.第二步当然就是交换了，由于我们从循环中跳出来的不是较小的那个数，而是较大的那一个，即右边的那一个，所以交换的时候的索引不是i而是i-1，而且是直接和它右边的那个元素交换吗？显然不是的吧，而应该是再次从右边开始，找到第一个比它大的数字交换。举个例子：上面的1,2,6,4我们找到需要交换的是2，但是我们就直接交换2和6吗？交换的是2和4吧，因为1624比1462要大吧，肯定不是下一个序列；

3.有很多人可能觉得到了第二步就已经完成任务了，其实还有更小的序列1426呢，是不是？1426是要比1462要小吧。可能很多人想到了，直接逆置一下不就完了吗？但是在这逆置开始的索引不是交换的那个位置，而是往后的一个索引。而且你发现，太巧了，题目说的如果没有找到下一个序列的话(即此序列已经是最大的了)，直接返回的是升序的序列，不就是我们说的逆置吗？

代码：

主体部分：

交换和逆置部分：