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,23,2,1 → 1,2,31,1,5 → 1,5,1
分析：找下一个排列。排列的过程可以理解为：
1、从右至左找到第一个不满足递增规律的数，例如 1 3 2 5 4，那么2应该被找出，记下标为left
2、从右至左找到第一个大于nums[left]的数，记下标为right
3、将nums[left]与nums[right]交换
4、将left右边的数字全部倒转
运行时间 16ms
1 class Solution { 2 public: 3 void nextPermutation(vector<int>& nums) { 4 if(nums.size() == 1) return; 5 if(nums.size() == 2){ 6 reverse(nums.begin(), nums.end()); 7 return; 8 } 9 10 //find left 11 int left = -1, right = nums.size() - 1; 12 for(int i = nums.size() - 1; i >= 1; i--){ 13 if(nums[i] > nums[i-1]){ 14 left = i - 1; 15 break; 16 } 17 } 18 if(left == -1){ 19 sort(nums.begin(), nums.end()); 20 return; 21 } 22 else{ 23 //find right 24 for(int j = nums.size() - 1; j > left; j--){ 25 if(nums[j] > nums[left]){ 26 right = j; 27 break; 28 } 29 } 30 //swap nums[left] and nums[right] 31 int temp = nums[left]; 32 nums[left] = nums[right]; 33 nums[right] = temp; 34 35 //reverse the numbers after left 36 int indexLeft = left + 1, indexRight = nums.size() - 1; 37 while(indexLeft < indexRight){ 38 int temp1 = nums[indexLeft]; 39 nums[indexLeft++] = nums[indexRight]; 40 nums[indexRight--] = temp1; 41 } 42 return; 43 } 44 } 45 };
原文：http://www.cnblogs.com/amazingzoe/p/4499037.html