题目描述
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
来源：力扣（LeetCode)
题解
输入的数组为nums[n-1]，本题目的解题思路是，从j=n-2往前遍历，判断nums[j+1,n-1]中是否有一个元素刚刚大于nums[j]的元素，如果有的话则交换。为了减少比较次数，将nums[j+1,n-1]首先进行从小到大排序，并且可以保证交换之后的nums[j+1,n-1]也是是一个从小到大的排序序列，进而保证nums是“下一个更大的排列”。
因为本方法从从后往前遍历的，第一次排序发生在j=n-3，因为j=n-2时没发生交换，所以nums[n-2]必定大于nums[n-1]。此后的循环便依赖于上一次的排序结果，所以只需在每次循环时将nums[j+1,n-1]的nums[j+1]移动到最后一位（firstToLast(）），便完成了排序。
例：nums = 6，4，5，3，2
当 j= 3 时，nums[j+1,n-1] = 2，不发生交换
当 j= 2 时，nums[j+1,n-1] = 3，2，执行firstToLast(），nums[j+1,n-1] = 2，3
当 j=1，时，nums[j+1,n-1] = 5，2，3， 执行firstToLast(），nums[j+1,n-1] = 2，3，5，此时发生交换，nums[j] = 5,nums[j+1,n-1] = 2，3，4
输出 6，5，2，3，4
最终，
执行用时 :4 ms, 在所有 cpp 提交中击败了99.88%的用户
内存消耗 :8.5 MB, 在所有 cpp 提交中击败了94.92%的用户
C++代码
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int i = nums.size()-2;
while(i >= 0){
firstToLast(i+1,nums);
for(int j = i+1; j < nums.size(); j++){
if(nums[j]>nums[i]){
swap(i,j,nums);
return;
}
}
i--;
}
firstToLast(0,nums);
}
void swap(int i,int j,vector<int>&nums){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
void firstToLast(int begin,vector<int>&nums){
int tmp = nums[begin];
for(int i=begin;i<nums.size()-1;i++){
nums[i] = nums[i+1];
}
nums[nums.size()-1] = tmp;
}
};
