#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;}