首页 > 代码库 > Permutation Sequence
Permutation Sequence
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.
参考:http://www.cnblogs.com/tenosdoit/p/3721918.html
C++实现代码:
#include<iostream>#include<string>#include<vector>using namespace std;class Solution {public: string getPermutation(int n, int k) { if(n==0) return ""; int total=factorial(n); string str=string("123456789").substr(0,n); string ret(n,‘ ‘); int i; for(i=0;i<n;i++) { int index; total=total/(n-i); index=(k-1)/total; ret[i]=str[index]; str.erase(index,1); k=k-index*total; } return ret; } int factorial(int n) { if(n==0) return 0; int i; int sum=1; for(i=1;i<=n;i++) sum*=i; return sum; }};int main(){ Solution s; cout<<s.getPermutation(3,5)<<endl;}
Permutation Sequence
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。