題目： LeetCode - 60. Permutation Sequence

解題思路

數學題。

參考解法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string getPermutation(int n, int k) {
        string result = "";
        string numbers = "123456789";

        vector<int> factorial(n, 1);
        for (int i = 2; i < n; ++i) {
            factorial[i] = i * factorial[i - 1];
        }

        --k; // for index
        for (int i = n; i >= 1; --i) {
            int j = k / factorial[i - 1];
            k %= factorial[i - 1];
            result += numbers[j];
            numbers.erase(j, 1);
        }

        return result;
    }
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        result = ''
        numbers = [str(i) for i in range(1, 11)]
        
        factorial = [1] * n
        for i in range(2, len(factorial)):
            factorial[i] = i * factorial[i - 1]
        
        # for index
        k -= 1
        for i in range(n, 0, -1):
            j = k // factorial[i - 1]
            k %= factorial[i - 1]
            result += numbers[j]
            del numbers[j]

        return result