leetcode解题: Permutation Sequence (60)

发表于 | 分类于

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):

“123”
“132”
“213”
“231”
“312”
“321”
Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

解法1： Math

数学题，解法就不重复了，第一位取值每(n - 1)!变化一位，第二位取值每（n - 2)% 变化一位。 通过k / (n - i)! 算出来的是index， 这就意味着每次取完一个数以后要把那个数删除。

C++

1
c++ 里面vector的初始化如果用vector<int> (n, initial_value)的形式要注意是“（”， 不是“{“， 花括号是给了一组初始的array

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) {
        vector<int> number ;
        int perm = 1;
        for (int i = 1; i <= n; ++i) {
            number.push_back(i);
            perm *= i;
        }
        
        k--;
        string res;
        for (int i = 0; i < n; ++i) {
            perm /= (n - i);
            int choosed = k / perm;
            k %= perm;
            res += to_string(number[choosed]);
            number.erase(number.begin() + choosed);
        }
        return res;
    }
};

Java

1