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,3,2,0]，那么此时指针iter是指向3的，它的前一个元素是1，那么须要前一个指针与它后面元素中大于1且最小的元素交换，这儿就是将1与[3,2,0]中最小的元素交换。所以1应该和2交换，然后再将剩下的元素进行升序排序就可以。

这儿因为数组是反向遍历的，所以能够使用使用stl中的反向迭代器。

runtime:12ms

class Solution {

public:

void nextPermutation(vector& nums) {

if(nums.size()<2) return ;

auto iter=nums.rbegin();

while(iter!=(nums.rend()-1)&&*iter<=*(iter+1))

iter++;

if(iter==nums.rend()-1)

sort(nums.begin(),nums.end());

else

{

auto upper=iter;

auto tmp=nums.rbegin();

for(;tmp!=iter;tmp++)

{

if(*tmp>*(iter+1))

{

if(*tmp<*upper)

{

upper=tmp;

}

}

}

swap(*(iter+1),*upper);

sort(nums.rbegin(),iter+1,greater());

}

}

};

查看原文