Tuesday, November 25, 2014

[LeetCode] Permutation Sequence

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 n = 3):
  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"
Given n and k, return the kth 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;
    }
};

24 comments:

  1. please write the logic of your code in English.

    ReplyDelete
  2. please write the logic of your code in English.

    ReplyDelete
  3. This comment has been removed by the author.

    ReplyDelete
  4. 求指导啊,为啥中间要k-- 啊?
    谢谢大神

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

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

      Delete