Given a collection of distinct numbers, return all possible permutations.
For example, [1,2,3] have the following permutations: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
求全排列，O(n!)复杂度。 使用递归，并使用一个标记数组，每次从数组里取出一个尚未被标记过的。
class Solution { public: vector<vector<int>> permute(vector<int>& nums) { vector<vector<int> > result; int n=nums.size(); vector<bool> visit(n,false); vector<int> temp; permutations(nums,temp,visit,result); return result; } //输出一个数组的全排列 void permutations(vector<int>& nums,vector<int>& temp,vector<bool>& visit,vector<vector<int> >& result){ if(temp.size()==nums.size()){ result.push_back(temp); return; } //遍历一个数组的所有元素 for(int i=0;i<nums.size();i++){ //找到第i个元素还没有被访问过 if(!visit[i]){ //向“栈”数组里加入这个元素 temp.push_back(nums[i]); visit[i]=true; permutations(nums,temp,visit,result); visit[i]=false; temp.pop_back(); } } } };Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example, [1,1,2] have the following unique permutations: [ [1,1,2], [1,2,1], [2,1,1] ] II是I的加强版，和上一个题目类似，这个要求去重。 按部就班地按照原来的去重方式，TLE 只能用自己写的nextPermutation，然后过了
class Solution { public: void nextPermutation(vector<int>& nums) { int n=nums.size(); if(n<=1) return; //从右往左找到第一个破坏升序的 int i; for(i=n-2;i>=0 && nums[i]>=nums[i+1];i--); //记录这个位置 int pivot=i; if(pivot>=0){ //从右往左找一个比这个数大的 for(i=n-1;i>=0 && nums[i]<=nums[pivot];i--); i=i>=0?i:0; //交换这两个数 int temp=nums[pivot]; nums[pivot]=nums[i]; nums[i]=temp; } //将从pivot开始以后的数据全部反向 for(int j=pivot+1,k=n-1;j<k && j<n-1 && k>=0;j++,k--){ int temp=nums[j]; nums[j]=nums[k]; nums[k]=temp; } } vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int> > result; int n=nums.size(); vector<bool> visit(n,false); vector<int> temp; sort(nums.begin(),nums.end()); //计算每个数都出现了多少次 unordered_map<int,int> map; for(int i=0;i<n;i++){ if(map.find(nums[i])!=map.end()){ map[nums[i]]++; } else map[nums[i]]=1; } //将这些键值对存入vector vector<pair<int,int> > pairs; for(auto iter = map.begin(); iter != map.end(); iter++) { pair<int,int> p; p.first=iter->first; p.second=iter->second; pairs.push_back(p); } permutations(n,temp,pairs,result); return result; // //不断执行nextPermutation,直到与第一个数据相等。 // vector<int> temp; // int n=nums.size(); // for(int i=0;i<n;i++) temp.push_back(nums[i]); // while(true){ // nextPermutation(nums); // result.push_back(nums); // int flag=0,i=0; // for(;i<n && temp[i]==nums[i];i++); // //说明全部的都相等 // if(i==n) break; // } // return result; // int n=nums.size(); // vector<bool> visit(n,false); // vector<int> temp; // sort(nums.begin(),nums.end()); // permutations(nums,temp,visit,result); // return result; } //输出一个数组的全排列 void permutations(int n,vector<int>& temp,vector<pair<int,int> > & pairs,vector<vector<int> >& result){ if(temp.size()==n){ result.push_back(temp); return; } //遍历键值数组的所有元素 for(int i=0;i<pairs.size();i++){ //统计数pairs[i].first在temp中出现了多少次 int count=0; for(int j=0;j<temp.size();j++){ if(pairs[i].first==temp[j]) count++; } //还有数据可以放 if(count<pairs[i].second){ temp.push_back(pairs[i].first); permutations(n,temp,pairs,result); temp.pop_back(); } } } };