题目链接：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, 3}，这个序列可能有留个可能的排列组合：123, 132, 213, 231, 312, 321。这些排列组合依据小于操作（<）符做字典顺序的排列。而这道题要求是求下一个排列。
首先，从最尾端开始往前寻找两个相邻元素，令第一个元素下标记为i，第二个元素下标记为ii，且满足num[i]<num[ii]。找到这样一组相邻元素后，再从数组尾端开始往前查找，找出第一个大于num[i]的元素，记其下标为j，交换i和j处的元素，再将ii处元素及其后面所有元素颠倒顺序。
参考自C++的next_permutation函数的实现（STL源码剖析）。
时间复杂度：O(n)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution
{
public:
void nextPermutation(vector<int> &num)
{
if(num.size() == 0 || num.size() == 1)
return ;
for(int i = num.size() - 1; ; )
{
int ii = i --;
if(num[i] < num[ii])
{
int j = num.size();
while(!(num[i] < num[-- j]));
swap(num[i], num[j]);
reverse(num.begin() + ii, num.end());
break;
}
if(i == 0)
{
reverse(num.begin(), num.end());
break;
}
}
}
};
或者采用迭代器实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution
{
public:
void nextPermutation(vector<int> &num)
{
if(num.size() == 0 || num.size() == 1)
return ;
auto i = num.end() - 1;
while(true)
{
auto ii = i --;
if(*i < *ii)
{
auto j = num.end();
while(!(*i < * -- j));
swap(*i, *j);
reverse(ii, num.end());
break;
}
if(i == num.begin())
{
reverse(i, num.end());
break;
}
}
}
};