首页 > 代码库 > leetcode - Permutation Sequence
leetcode - 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.
#if 0 class Solution { public: std::string getPermutation(int n, int k) { std::string s; for (int i = 0; i < n; i++) { s.push_back(i+1+'0'); } int cnt = 0; do { cnt++; } while (std::next_permutation(s.begin(),s.end()) && cnt < k); #if 0 std::cout << s << std::endl; #endif // 1 return s; } }; #endif // The code TLE. (一般解法) #if 1 class Solution { public: std::string getPermutation(int n, int k) { std::vector<int> vec(n,0); int t = 1; for (int i = 0; i < n; i++) { vec[i] = i + 1; t *= i + 1; } std::string s; k--; for (int i = 0; i < n; i++) { t /= n - i; s.push_back(vec[k / t] + '0'); vec.erase(vec.begin() + k / t); k %= t; } #if 0 std::cout << s << std::endl; #endif // 1 return s; } }; #endif // 1
leetcode - Permutation Sequence
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。