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\)
1
class Solution {
2
    public String getPermutation(int n, int k) {
3
        if (n <= 0 || k <= 0) {
4
            return "";
5
        }
6
​
7
        StringBuilder res = new StringBuilder();
8
        StringBuilder nums = new StringBuilder();
9
​
10
        for (int i = 1; i <= n; i++) {
11
            nums.append(i);
12
        }
13
​
14
        --k;
15
        int[] factorial = new int[n + 1];
16
        factorial[0] = 1;
17
        for (int i = 1; i <= n; i++) {
18
            factorial[i] = factorial[i - 1] * i;
19
        }
20
​
21
        for (int i = 1; i <= n; i++) {
22
            int index = k / factorial[n - i];
23
            res.append(nums.charAt(index));
24
            nums.deleteCharAt(index);
25
            k -= index * factorial[n - i];
26
        }
27
        return res.toString();
28
    }
29
}
Copied!
3. Time & Space Complexity
Math: 时间复杂度O(n), 空间复杂度O(n)

52 N-Queens II

77 Combinations

Last modified 2yr ago

Copy link

Contents

60. Permutation Sequence

1. Question

2. Implementation

3. Time & Space Complexity

60. Permutation Sequence​

1. Question

2. Implementation

3. Time & Space Complexity

60. Permutation Sequence