60. Permutation Sequence

Problem:

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.

7/24/2018 update:
The purpose of removing the added element is that, each time we reduce k, we actually get the number from new order.1234 for instance, the index is always 0 everytime.
--------------------------------------------------------------------------------------------------------------------------------------------

Analysis:

这种数学类的题在面试里面做出来的机会很渺茫啊。这道题想到于矩阵的扩展。如果n == 4,那么可以转换成找 6*4 matrix里面第k个数。

http://www.cnblogs.com/grandyang/p/4358678.html

Solution:

Note k has to subtract by 1, because index is zero based. 

class Solution {
    public String getPermutation(int n, int k) {
        List<Integer> nums = new ArrayList<>();
        int[] factor = new int[n];
        factor[0] = 1;
        for (int i = 1; i < n; i++) {
            factor[i] = factor[i - 1] * i;
        }

        for (int i = 1; i <= n; i++) {
            nums.add(i);
        }
        
        k--;

        StringBuilder sb = new StringBuilder();
        for (int i = n; i > 0; i--) {
            int index = k/factor[i - 1];
            k %= factor[i - 1];
            sb.append(nums.get(index));
            nums.remove(index);
        }
        return sb.toString();
    }
}