[Leetcode Solution] Permutation Sequence

Analysis 

• At first think about the search, it should be kind of slow. And actually it exceeds the time limits
• The problem is only need to get the k-th element, so we can directly calculate what the k-th element is, rather then enumerate all the elements. The idea is like carry. 
• If we have n integers [1..n], and the number of permutation starting from each integer is (n-1)!, thus we can calculate the first number of required permutation according to k/(n-1).
• Then we can update the k, and do this procedure recursively

Note

• Dealing with something like carry, or divide the region, given the each region's size S, and the k-th number, ask which region this number located in. Make the k start from 0 and then use k/S to get it

Code