首页 > 代码库 > Permutation Sequence
Permutation Sequence
这题关键是要理解数的顺序怎么通过递推得到。以题目中给出的n = 3为例：
我们看到，总共是3！ = 6 个数，
123
132
213
231
312
321
以1、2和3开始的数各有两个（2!个），我们可以推广一下，对于n!个数，以1、2……n开头的数各有(n - 1)!个，而开头的数小的，总是排在前面。当我们要找到第k个数的时候，首先要确定，它是以几开头的，而我们可以知道的是以i开头的数的最小序号是(i - 1) *（n - 1）! + 1，于是依次递推，就能得到最终的数：
如果数字是完整的从1\2到n，那以i开头就是指开头的数字是i,但是在确定了第一个数之后，1……n的数字中缺了一个（例如是n - 2），这时我们说以i开头就是指以排在第i位的数开头。
string getPermutation(int n, int k){ char num[] = {‘0‘, ‘1‘, ‘2‘, ‘3‘, ‘4‘, ‘5‘, ‘6‘, ‘7‘, ‘8‘, ‘9‘}; string result; vector<int> table(10); table[0] = 1; for (int i = 1; i < 10; i++){ table[i] = i * table[i - 1]; } vector<int> seq; seq.push_back(0); for (int i = 1; i < n + 1; i++) seq.push_back(i); for (int i = n - 1; i >= 0; i--){ int x = ((k - 1) / (table[i]) + 1); k -= (x - 1) * table[i]; result.push_back(num[seq[x]]); seq.erase(seq.begin() + x); } return result;}
Permutation Sequence
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。