The set

`[1,2,3,…,`*n*]

contains a total of *n*! unique permutations.
By listing and labeling all of the permutations in order,

We get the following sequence (ie, for

We get the following sequence (ie, for

*n*= 3):`"123"`

`"132"`

`"213"`

`"231"`

`"312"`

`"321"`

Given

*n*and*k*, return the*k*th permutation sequence.
Note: Given

*n*will be between 1 and 9 inclusive.
同样先通过举例来获得更好的理解。以n = 4，k = 9为例：

1234

1243

1324

1342

1423

1432

2134

2143

2314 <= k = 9

2341

2413

2431

3124

3142

3214

3241

3412

3421

4123

4132

4213

4231

4312

4321

最高位可以取{1, 2, 3, 4}，而每个数重复3! = 6次。所以第k=9个permutation的s[0]为{1, 2, 3, 4}中的第9/6+1 = 2个数字s[0] = 2。

而对于以2开头的6个数字而言，k = 9是其中的第k' = 9%(3!) = 3个。而剩下的数字{1, 3, 4}的重复周期为2! = 2次。所以s[1]为{1, 3, 4}中的第k'/(2!)+1 = 2个，即s[1] = 3。

对于以23开头的2个数字而言，k = 9是其中的第k'' = k'%(2!) = 1个。剩下的数字{1, 4}的重复周期为1! = 1次。所以s[2] = 1.

对于以231开头的一个数字而言，k = 9是其中的第k''' = k''/(1!)+1 = 1个。s[3] = 4

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | class Solution { public: string getPermutation(int n, int k) { string ret; vector<int> factorial(n,1); vector<char> num(n,1); for(int i=1; i<n; i++) factorial[i] = factorial[i-1]*i; for(int i=0; i<n; i++) num[i] = (i+1)+'0'; k--; for(int i=n; i>=1; i--) { int j = k/factorial[i-1]; k %= factorial[i-1]; ret.push_back(num[j]); num.erase(num.begin()+j); } return ret; } }; |

please write the logic of your code in English.

ReplyDeleteyou should learn Chinese then

Deleteyou should learn Chinese then

Deleteyou should learn Chinese then

Deleteyou should learn Chinese then

DeleteLOLOL

DeleteHahahahah. Poor guy :)

DeleteSorry, Chinese exclusive

DeleteThis comment has been removed by the author.

DeleteYou should learn Chinese, haha

DeleteYou should learn Chinese then.

Deleteplease write the logic of your code in English.

ReplyDeleteThis comment has been removed by the author.

DeleteThis comment has been removed by the author.

DeleteLearn Chinese~~

Deletehaha

DeleteThis comment has been removed by the author.

ReplyDeletegood!

ReplyDelete求指导啊，为啥中间要k-- 啊？

ReplyDelete谢谢大神

考虑特殊情况，比如如果输入为n=1,k=1,这种情况，先执行k--， index = k/factorial[i-1] = 0, 才可以返回1;

Delete我觉得你说的不对，这个算法如果输入是k本来算出来的就是第k+1个排序。所以要--k，这样输入是k-1，得出来的就是第k个排序。

Delete