描述 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.
分析 簡單的，可以用暴力枚舉法，調(diào)用 k ? 1 次 next_permutation()。 暴力枚舉法把前 k 個排列都求出來了，比較浪費，而我們只需要第 k 個排列。
利用康托編碼的思路，稍后細(xì)述。
代碼
class Solution {public: string getPermutation(int n, int k) { string s(n, '0'); for (int i = 0; i < n; ++i) s[i] += i + 1; for (int i = 0; i < k - 1; ++i) next_permutation(s.begin(), s.end()); return s; } template<typename BidiIt> bool next_permutation(BidiIt first, BidiIt last) { // Get a reversed range to simplify reversed traversal. const auto rfirst = reverse_iterator<BidiIt>(last); const auto rlast = reverse_iterator<BidiIt>(first); // Begin from the second last element to the first element. auto pivot = next(rfirst); // Find `pivot`, which is the first element that is no less than its // successor. `PRev` is used since `pivort` is a `reversed_iterator`. while (pivot != rlast && *pivot >= *prev(pivot)) ++pivot; // No such elemenet found, current sequence is already the largest // permutation, then rearrange to the first permutation and return false. if (pivot == rlast) { reverse(rfirst, rlast); return false; } // Scan from right to left, find the first element that is greater than // `pivot`. auto change = find_if(rfirst, pivot, bind1st(less<int>(), *pivot)); swap(*change, *pivot); reverse(rfirst, pivot); return true; }};新聞熱點
疑難解答
