LeetCode 31. 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 and use only constant 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，3则下一个是将2，3交换后得到的1，3，2；比如3，2，1没有比它更大的了，所以返回最小的1，2，3.
以下面这个例子解释：
1　　2　　7　　4　　3　　1
则下一个排列应该是：
1　　3　　1　　2　　4　　7
那么是如何得到的呢，我们通过观察原数组可以发现，如果从末尾往前看，数字逐渐变大，到了2时才减小的，然后我们再从后往前找第一个比2大的数字，是3，那么我们交换2和3，再把此时3后面的所有数字转置一下即可，步骤如下：
1　　2　　7　　4　　3　　1

1　　2　　7　　4　　3　　1

1　　3　　7　　4　　2　　1

1　　3　　1　　2　　4　　7
代码实现：
[cc lang=”C++”]
class Solution {
public:
void nextPermutation(vector& nums) {
int i, j, len = nums.size();
for(i=len-2;i>=0;i–)
{
if(nums[i+1] > nums[i])//从后向前找到第一个不满足升序的数字a
{
for(j=len-1;j>i;j–)//从后向前找到第一个比当前数字a大的数字b
{
if(nums[j] > nums[i])
break;
}
swap(nums[i],nums[j]);//交换数字a和b
reverse(nums.begin() + i +1, nums.end());//将a后面的数字逆序
return;
}
}
reverse(nums.begin(), nums.end());//如果当前数字最大，则整体逆序，返回最小的排列
}
};
[/cc]

解法2:
思路跟上面相同，代码更简洁一点。
[cc lang=”C++”]
class Solution {
public:
void nextPermutation(vector& nums) {
int len = nums.size();
int i = len -2,j=len-1;
while(i>=0 && nums[i]>=nums[i+1])
i –;
if(i >= 0)
{
while(nums[j]<=nums[i]) j --; swap(nums[i], nums[j]); } reverse(nums.begin() + i + 1, nums.end()); } }; [/cc] 如果现在的排列全是降序的，比如5，4，3，2，1 这种情况，则执行完降序判断之后，i=-1.此时nums.begin() + i + 1 = nums.begin()。所以最后相当于直接将整个数组做翻转了。
参考：https://www.cnblogs.com/grandyang/p/4428207.html