#include <iostream>#include <stdio.h>#include <vector>#include <algorithm>using namespace std;/*問(wèn)題: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分析:此問(wèn)題要求產(chǎn)生按照字典順序產(chǎn)生下一個(gè)較大的數(shù)字排列。如果已經(jīng)是最大的數(shù)字排列則返回最小的數(shù)字排列。關(guān)于排列問(wèn)題，可以通過(guò)遞歸擺放的形式產(chǎn)生。但是遞歸擺放尤其要注意數(shù)字中有重復(fù)數(shù)字的情況。一種方法是：從初始狀態(tài)進(jìn)行處理，遞歸到輸出當(dāng)前輸入的排列后，則記錄當(dāng)前輸入排列后面下一個(gè)排列為最終結(jié)果。但是這樣會(huì)耗費(fèi)O(n!)時(shí)間，令外一種方法是下一個(gè)排列應(yīng)該比上一個(gè)排列稍微大一點(diǎn)，也就是在原有排序的基礎(chǔ)上從后向前找到：如果當(dāng)前數(shù)大于前面一個(gè)數(shù)就交換。如果整個(gè)排列的數(shù)是逆序的，說(shuō)明已經(jīng)是最大的，則重新排序一下變成最小的。輸入：3(元素個(gè)數(shù))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 報(bào)錯(cuò):Input:[1,3,2]Output:[3,1,2]Expected:[2,1,3]問(wèn)題出在：不能簡(jiǎn)單地將當(dāng)前數(shù)>前面的一個(gè)數(shù)進(jìn)行調(diào)換后處理，需要進(jìn)行處理。也就是說(shuō)可以將這些數(shù)生成排列，進(jìn)行排序，找到當(dāng)前數(shù)的下一個(gè)數(shù)，時(shí)間復(fù)雜度為O(n!)關(guān)鍵:1需要找到需要調(diào)換的較小的數(shù)字下標(biāo),該下標(biāo)是從后向前，存在nums[i] < nums[i+1]中的下標(biāo)i，注意這里不是讓nums[i] 和 nums[i+1]調(diào)換，而是需要再次從后向前尋找到nums[k] > nums[i],這里表明nums[k]是大于nums[i]中的最小數(shù)字，符合下一個(gè)排列一定是比原來(lái)排列稍大的條件，注意需要將nums中k+1~len-1的數(shù)組元素進(jìn)行逆置，因?yàn)檫@一段元素已經(jīng)是降序不是最小的*/class Solution {public:    void nextPermutation(vector<int>& nums) {        if(nums.empty())		{			return;		}		//非逆序，則從后向前：尋找到第一次出現(xiàn)：當(dāng)前數(shù)值>前面一個(gè)數(shù)的位置，該數(shù)字就是需要替換的較小數(shù)		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;			}		}		//如果是逆序，則排序。牛逼，這用數(shù)組下標(biāo)判斷		if(-1 == k)		{			sort(nums.begin() , nums.end());			return;		}		//再次從后向前，尋找到第一次大于待替換的數(shù)值(從后向前默認(rèn)是升序132,比如這里應(yīng)該找到2比最前面帶替換的1大，所以交換后變成231，		//但是交換后后面變成標(biāo)準(zhǔn)的降序如31，此時(shí)已經(jīng)確保首位變大，后面降序應(yīng)該變成升序，因此需要逆置		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;//要退出			}		}		//將轉(zhuǎn)換后的較大位之后部分逆置，使其變成最小值		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;}