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 k th permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
分析:
首先想到的暴力法,逐个的求排列,直到找到第k个排列,提交之后会超时,在网上搜索之后发现可以直接构造出第k个排列,以n = 4,k = 17为例,数组src = [1,2,3,...,n]。
第17个排列的第一个数是什么呢:我们知道以某个数固定开头的排列个数 = (n-1)! = 3! = 6, 即以1和2开头的排列总共6*2 = 12个,12 < 17, 因此第17个排列的第一个数不可能是1或者2,6*3 > 17, 因此第17个排列的第一个数是3。即第17个排列的第一个数是原数组(原数组递增有序)的第m = upper(17/6) = 3(upper表示向上取整)个数。
第一个数固定后,我们从src数组中删除该数,那么就相当于在当前src的基础上求第k - (m-1)*(n-1)! = 17 - 2*6 = 5个排列,因此可以递归的求解该问题。
代码实现中注意一个小细节,就是一开始把k--,目的是让下标从0开始,这样下标就是从0到n-1,不用考虑n时去取余,更好地跟数组下标匹配。
思路:有一种方法,我们可以递归求解出所有的排列,然后取出第k个,但是这么操作,既复杂,也没有必要。
我们来一起找找数学规律,n个数的排列总共有n!个组合,基于这个性质我们可以得到某一位对应的数字是哪一个。如,当前长度是n,我们知道每个相同起始元素都对应(n-1)!个排列,也就是每隔(n-1)!个排列就会按照大小顺序更换一个起始元素。因此,我们只要对当前的k对(n-1)!取余,得到的数字就是当前剩余数组的index, k /(n-1)!就是当前元素。如此递归下去,知道数组中没有元素。我们需要维护一个数组记录当前的元素,每次得到一个元素加入结果数组,就要把它从剩余数组中移除,剩余数组重新排序,接下来依然按照index取元素。
假设有n个元素,第K个permutation是
[cpp] view plain copy if(round > 0) factorial /= round; a1, a2, a3, ..... ..., an 那么a1是哪一个数字呢? 那么这里,我们把a1去掉,那么剩下的permutation为 a2, a3, .... .... an, 共计n-1个元素。 n-1个元素共有(n-1)!组排列,那么这里就可以知道 设变量K1 = K a1 = K1 / (n-1)! 同理,a2的值可以推导为 a2 = K2 / (n-2)! K2 = K1 % (n-1)! ....... a(n-1) = K(n-1) / 1! K(n-1) = K(n-2) /2! an = K(n-1)Attention:
1. k--; 让下标从0开始,这样就统一了下标和数组下标索引。
2. 每次得到的元素,转成字符后,添加到结果字符串中。用加‘0’的方式
[cpp] view plain copy ret += ('0' + nums[index]); //转成字符添加进字符串 3. vector的 erase函数 删除后,会改变容器大小和排序。
iterator erase (const_iterator position); iterator erase (const_iterator first, const_iterator last);
参数必须是迭代器。
[cpp] view plain copy nums.erase(nums.begin() + index); //参数必须是迭代器 4. 再递减 (n-1)!时,需要判断分母是否大于0.
[cpp] view plain copy if(round > 0) factorial /= round; 5. 我们需要判断到round = 0, 从 (n-1)! 到 0!, 总共添加n回,才能得到结果字符串
[cpp] view plain copy while(round >= 0) 复杂度:O(N), 进行N各回合。
实现代码:
class Solution {public: string getPermutation(int n, int k) { if(n <= 0) return ""; k--; //转换成从0开始 string ret; int factorial = 1; //计算(n-1)! for(int i = 2; i < n; i++) { factorial *= i; } vector<int> nums; for(int i = 1; i <= n; i++) { nums.push_back(i); } int round = n - 1; while(round >= 0) //循环n次将n个数全部放入ret中; { int index = k / factorial; k %= factorial; ret += ('0' + nums[index]); //转成字符添加进字符串 nums.erase(nums.begin() + index); //参数必须是迭代器 if(round > 0) factorial /= round; round--; } return ret; }};