60 Permutation Sequence

60. Permutation Sequence

1. Question

The set[1,2,3,…,n]contains a total ofn! 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"

Given n and k, return the kth permutation sequence.

2. Implementation

(1) Math

思路 https://leetcode.com/problems/permutation-sequence/discuss/22507/%22Explain-like-I'm-five%22-Java-Solution-in-O(n\)

class Solution {
    public String getPermutation(int n, int k) {
        if (n <= 0 || k <= 0) {
            return "";
        }

        StringBuilder res = new StringBuilder();
        StringBuilder nums = new StringBuilder();

        for (int i = 1; i <= n; i++) {
            nums.append(i);
        }

        --k;
        int[] factorial = new int[n + 1];
        factorial[0] = 1;
        for (int i = 1; i <= n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }

        for (int i = 1; i <= n; i++) {
            int index = k / factorial[n - i];
            res.append(nums.charAt(index));
            nums.deleteCharAt(index);
            k -= index * factorial[n - i];
        }
        return res.toString();
    }
}

3. Time & Space Complexity

Math: 时间复杂度O(n), 空间复杂度O(n)