leecode 解题总结：31. Next Permutation

#include <iostream>#include <stdio.h>#include <vector>#include <algorithm>using namespace std;/*问题: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分析:此问题要求产生按照字典顺序产生下一个较大的数字排列。如果已经是最大的数字排列则返回最小的数字排列。关于排列问题，可以通过递归摆放的形式产生。但是递归摆放尤其要注意数字中有重复数字的情况。一种方法是：从初始状态进行处理，递归到输出当前输入的排列后，则记录当前输入排列后面下一个排列为最终结果。但是这样会耗费O(n!)时间，令外一种方法是下一个排列应该比上一个排列稍微大一点，也就是在原有排序的基础上从后向前找到：如果当前数大于前面一个数就交换。如果整个排列的数是逆序的，说明已经是最大的，则重新排序一下变成最小的。输入：3(元素个数)1 2 331 1 133 2 131 1 531 2 131 3 2输出:1 3 21 1 11 2 31 5 12 1 12 1 31 报错:Input:[1,3,2]Output:[3,1,2]Expected:[2,1,3]问题出在：不能简单地将当前数>前面的一个数进行调换后处理，需要进行处理。也就是说可以将这些数生成排列，进行排序，找到当前数的下一个数，时间复杂度为O(n!)关键:1需要找到需要调换的较小的数字下标,该下标是从后向前，存在nums[i] < nums[i+1]中的下标i，注意这里不是让nums[i] 和 nums[i+1]调换，而是需要再次从后向前寻找到nums[k] > nums[i],这里表明nums[k]是大于nums[i]中的最小数字，符合下一个排列一定是比原来排列稍大的条件，注意需要将nums中k+1~len-1的数组元素进行逆置，因为这一段元素已经是降序不是最小的*/class Solution {public:    void nextPermutation(vector<int>& nums) {        if(nums.empty())		{			return;		}		//非逆序，则从后向前：寻找到第一次出现：当前数值>前面一个数的位置，该数字就是需要替换的较小数		int len = nums.size();		int k = -1;		for(int i = len - 2 ; i >= 0; i--)		{			if(nums.at(i) < nums.at(i+1))			{				k = i;				break;			}		}		//如果是逆序，则排序。牛逼，这用数组下标判断		if(-1 == k)		{			sort(nums.begin() , nums.end());			return;		}		//再次从后向前，寻找到第一次大于待替换的数值(从后向前默认是升序132,比如这里应该找到2比最前面带替换的1大，所以交换后变成231，		//但是交换后后面变成标准的降序如31，此时已经确保首位变大，后面降序应该变成升序，因此需要逆置		for(int i = len - 1 ; i >= 0 ; i --)		{			if(nums.at(i) > nums.at(k))			{				int temp = nums.at(i);				nums.at(i) = nums.at(k);				nums.at(k) = temp;				break;//要退出			}		}		//将转换后的较大位之后部分逆置，使其变成最小值		reverse(nums.begin() + k + 1  , nums.end());    }};void PRint(vector<int>& datas){	if(datas.empty())	{		cout << "no result" << endl;		return;	}	int size = datas.size();	for(int i = 0 ; i < size ; i++)	{		cout << datas.at(i) << " ";	}	cout << endl;}void process(){	int num;	int value;	vector<int> datas;	Solution solution;	while(cin >> num)	{		datas.clear();		for(int i = 0 ; i < num ; i++)		{			cin >> value;			datas.push_back(value);		}		solution.nextPermutation(datas);		print(datas);	}}int main(int argc , char* argv[]){	process();	getchar();	return 0;}