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
Solution:
从后往前扫一遍，如果当前元素比它之后的所有元素都大，那么我们不可能交换产生更大的序列，此时我们把从该元素开始到最后的所有元素按升序排列。
如果当前元素比它之后的最大元素小，那么找到比它大的元素中最小者，与之交换，产生的新序列为所需。PS, 当我们扫描第i个元素时，从i + 1到最后，
元素是按照升序排列的。所以，当最后没有完成交换时，所有元素回到升序排列。
class Solution { public: void nextPermutation(vector<int> &num) { if(num.size() < 2) return; int curMax = num[num.size() - 1]; for(int i = num.size() - 1; i >= 0;i--) { if(num[i] < curMax) { int tmp = num[i]; int j = 0; for(j = i + 1; j < num.size();j++) { if(tmp < num[j]) { num[i] = num[j]; num[j] = tmp; return; } } if(j == num.size()) { num[j - 1] = tmp; return; } } else { curMax = num[i]; for(int j = i + 1; j < num.size();j++) num[j - 1] = num[j]; num[num.size() - 1] = curMax; } } } };
[LeetCode] Next Permutation,布布扣,bubuko.com
原文：http://www.cnblogs.com/changchengxiao/p/3614477.html