Permutation Sequence

https://leetcode.com/problems/permutation-sequence/description/

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, forn= 3):

1. "123"

2. "132"

3. "213"

4. "231"

5. "312"

6. "321"

Givennandk, return thekthpermutation sequence.

Thoughts

把首位固定, 那每组会有(N-1)!个数. 我们让k/(N - 1)!就可以知道kth的第一个数是多少. 这时我们要把第一个数从nums中移出去, 更新k = k % (N - 1)!. 同理判断第二个数的index是多少. 依次类推下去.

Code

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

        StringBuilder sb = new StringBuilder();
        k--;
        for (int i = 1; i <= n; i++) {
            int index = k / fac[n - i];
            sb.append(String.valueOf(numbers.get(index)));
            k = k % fac[n - i];
            numbers.remove(index);
        }

        return sb.toString();
    }
}

Analysis

Errors: 1. k在运算前必须-1. 时空复杂度为O(N).