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,2→2,1,2       (个人补充) 

题目的意思是：123的全排列按字典顺序为：

123  132 213 231 312 321

如果输入其中某一个序列，返回它的下一个序列。如：输入：213  输出：231 ；输入：321  输出：123

算法思想：举例如下

输入：1  4  6  5  3  2

step1：从右往左找到第一个破坏升序(非严格)的元素，此例中为4.记下标为 i

step2:  依然从右往左,找到第一个大于4的元素，此例中5，交换4和5.

step3：从i+1到最右端，逆置。6 4 3 2   to   2 3 4 6 

 so,1 5 2 3 4 6 即为所求。

class Solution {
public:
    void nextPermutation(vector<int> &num) {
		 if (num.size() == 0) return;
		 int i = num.size()-1;
		 int j;
		 while(i>0 && num[i] <= num[i - 1]){
				 i--;
		 }
		 if (i != 0){
			 j = num.size() - 1;
			 while (num[j] <= num[i-1])
				 j--;
			
			swap(num[i-1],num[j]);	
		 }//if
		 j = num.size() - 1;
		 while (i < j){
			 swap(num[i], num[j]);
			 i++; j--;
		 }
	 }

	 void swap(int &a, int &b){
		 int c;
		 c = a; a = b; b = c; 
	 }
};

LeetCode之Next Permutation,布布扣,bubuko.com

LeetCode之Next Permutation

原文：http://blog.csdn.net/smileteo/article/details/21894497