LeetCode: Permutation Sequence

这题的难度在编程，一开始想到的dfs过不了large，第二次想到网上的正确答案的思路，不过没有编出来，然后只好找答案了

 1 class Solution {
 2 public:
 3     string getPermutation(int n, int k) {
 4         // Start typing your C/C++ solution below
 5         // DO NOT write int main() function
 6         string ret = "";
 7         int time = 1;
 8         for (int i = 1; i <= n; i++) {
 9             ret += (char)('0'+i);
10             time *= i;
11         }
12         k--;
13         k %= time;
14         time /= n;
15         for (int i = 0; i < n-1; i++) {
16             int select = k / time;
17             k %= time;
18             time /= n - i - 1;
19             int tmp = ret[i + select];
20             for (int j = select; j > 0; j--) ret[i+j] = ret[i+j-1];
21             ret[i] = tmp;
22         }
23         return ret;
24     }
25 };