目录
一、递归求全排列
二、next_permutation实现
三、康托展开
一、递归求全排列
46. 全排列
class Solution {vector<vector<int>> ans;public:vector<vector<int>> permute(vector<int>& nums) {perm(nums, 0, nums.size() - 1);return ans;}void perm(vector<int> nums, int left, int right) {if (left == right)ans.push_back(nums);else {for (int i = left; i <= right; i++) {swap(nums[left], nums[i]);perm(nums, left + 1, right);//swap(nums[left], nums[i]);//不是引用的话,不用换回来}}}
};
47. 全排列 II
class Solution {vector<vector<int>> ans;public:vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());perm(nums, 0, nums.size() - 1);return ans;}void perm(vector<int> nums, int left, int right) {if (left == right)ans.push_back(nums);else {for (int i = left; i <= right; i++) {if (i != left && nums[left] == nums[i]) continue; swap(nums[left], nums[i]);perm(nums, left + 1, right);// swap(nums[left], nums[i]);}}}
};
二、next_permutation实现
递归总显得没有抓住这类问题的本质；next_permutation是求下一个全排列的库函数，我们要弄清它的原理。
class Solution {
public:template < typename T>bool Next_permutation(T first,T last){if(first == last)return false;//空区间T i = first;i++;if(i == last)return false;//1个元素i = last;i--;while(1){T ii = i;i--;//逆序找出第一个 *i<*ii;if(*i < *ii){T j = last;while(!(*i < *--j));//倒序找到第一个比*i大的元素iter_swap(i,j);//交换*i，*jreverse(ii,last);//ii之后的全部逆序return true;}if(i == first){//进行到最前面了，全部逆序返回falsereverse(first,last);return false;}}}vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(),nums.end());std::vector<std::vector<int> > ans;do{ans.push_back(nums);}while(Next_permutation(nums.begin(),nums.end()));return ans;}};
31. 下一个排列
class Solution {
public:template < typename T>bool Next_permutation(T first,T last){if(first == last)return false;//空区间T i = first;i++;if(i == last)return false;//1个元素i = last;i--;while(1){T ii = i;i--;//逆序找出第一个 *i<*ii;if(*i < *ii){T j = last;while(!(*i < *--j));//倒序找到第一个比*i大的元素iter_swap(i,j);//交换*i，*jreverse(ii,last);//ii之后的全部逆序return true;}if(i == first){//进行到最前面了，全部逆序返回falsereverse(first,last);return false;}}}void nextPermutation(vector<int>& nums) {Next_permutation(nums.begin(),nums.end());return;}
};
三、康托展开
60. 第k个排列
当然这道题，可以多次调用next_permutation；但是这道题本质是要我们了解 康托展开 的。
class Solution {
public:string getPermutation(int n, int k) {string s;string ans;for(int i = 1;i<=n;++i)s+=('0'+i);// if(k == 1)return s;int f[10];f[0] = 1;for(int i = 1;i<=9;++i)f[i] = f[i-1]*i;k--;for(int i = n;i>=1;--i){int r = k % f[i-1];int t = k / f[i-1];k = r;sort(s.begin(),s.end());ans.push_back(s[t]);s.erase(s.begin()+t);} return ans;}};