给出一组可能包含重复项的数字,返回该组数字的所有排列。结果以字典序升序排列。
数据范围: ,数组中的值满足
要求:空间复杂度 ,时间复杂度
class Solution { vector<vector<int>> res; public: vector<vector<int> > permuteUnique(vector<int> &num) { sort(num.begin(),num.end()); solve(num,0); sort(res.begin(),res.end()); res.erase(unique(res.begin(),res.end()),res.end()); return res; } void solve(vector<int>& num,int step){ if(step==num.size()){ res.push_back(num); return; } solve(num,step+1); for(int i=step+1;i<num.size();++i){ if(num[i]==num[step])continue; swap(num[step],num[i]); solve(num,step+1); swap(num[step],num[i]); } } };
// 回溯 class Solution { public: vector<vector<int>> res; vector<vector<int>> permuteUnique(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<int> temp; vector<bool> visited(nums.size(), false); // 标记访问 DFS(temp, nums, visited); return res; } void DFS(vector<int>& temp, vector<int>& nums, vector<bool>& visited) { if(temp.size() == nums.size()) { res.push_back(temp); return; } for(int i = 0; i < nums.size(); ++i) { if(visited[i]) continue; // 去重 if(i != 0 && nums[i] == nums[i-1] && !visited[i - 1]) continue; visited[i] = true; temp.push_back(nums[i]); DFS(temp, nums, visited); temp.pop_back(); visited[i] = false; // 回溯 } } };
import java.util.*; public class Solution { ArrayList<ArrayList<Integer>> res=new ArrayList<>(); public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) { int n=num.length; Arrays.sort(num); boolean[]visited=new boolean[n]; dfs(num,visited,new ArrayList<Integer>()); Collections.sort(res, new Comparator<ArrayList<Integer>>() { @Override public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) { for(int i=0;i<o1.size();i++){ if(o1.get(i)>o2.get(i)){ return 1; }else if(o1.get(i)<o2.get(i)){ return -1; } } return 0; } }); return res; } public void dfs(int[]num,boolean[]visited,List<Integer>temp){ if(temp.size()==num.length) res.add(new ArrayList<>(temp)); for(int i=0;i<num.length;i++){ if(visited[i]) continue; if(i>0&&num[i]==num[i-1]&&!visited[i-1]) continue; visited[i]=true; temp.add(num[i]); dfs(num,visited,temp); visited[i]=false; temp.remove(temp.size()-1); } } }
import java.util.*; public class Solution { ArrayList<ArrayList<Integer>> ans = new ArrayList<>(); ArrayList<Integer> list = new ArrayList<>(); public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) { Arrays.sort(num); boolean[] visited = new boolean[num.length]; recu(num, visited, 0); return ans; } public void recu(int[] num, boolean[] visited, int count){ if(count == num.length){ ans.add(new ArrayList(list)); return; } for(int i = 0; i < num.length; i++){ if(i>0 && !visited[i] && !visited[i-1] && num[i] == num[i-1]) continue; if(!visited[i]){ visited[i] = true; list.add(num[i]); recu(num, visited, count+1); visited[i] = false; list.remove(list.size()-1); } } } }
import java.util.*; public class Solution { ArrayList<ArrayList<Integer>> ress= new ArrayList<>(); boolean[] visited; public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) { if (num == null || num.length == 0) { return ress; } ArrayList<Integer> res = new ArrayList<>(); Arrays.sort(num); visited = new boolean[num.length]; dfs (res, num); return ress; } public void dfs (ArrayList<Integer> res, int[] num) { if (res.size() == num.length) { // 注意 如果这里直接add res的话,加的只会是res的指针,到最后,res肯定会回到最初的起点, // 所以会出现也结果个数相同的空集合,这个时候需要另外分配内存给中间结果并存入 ress.add(new ArrayList<>(res)); return; } // 每次回溯的时候,又回到了新一轮的选择,所以每个选择都有被判断的机会,这里用的是for循环实现, // 但只要是回溯,就一定会有一个作选择的地方, // 而且都是全选(每一层的循环选一个,走到最后一个选择就原路返回一层,以此类推),只是有顺序而已 for (int i = 0; i < num.length; i++) { if (visited[i]) { continue; } if (i > 0 && num[i] == num[i - 1] && !visited[i - 1]) { continue; } visited[i] = true; res.add(num[i]); dfs(res, num); res.remove(res.size() - 1); visited[i] = false; } } }
class Solution { public: vector<vector<int> > permuteUnique(vector<int> &num) { vector<vector<int>> res; int len=num.size(); dfs(num,0,len,res); return res; } void dfs(vector<int> num, int index, int len, vector<vector<int>>& res) { if(index==len ) { res.push_back(num); return ; } set<int> t; for(int i=index;i<len;i++) { if(t.find(num[i])!=t.end()) { continue; } t.insert(num[i]); //!!放在交换前(一开始写在交换后,WA了……) swap(num[i],num[index]); //交换 dfs(num,index+1,len,res); swap(num[i],num[index]); //复原 } } };
import java.util.*; public class Solution { public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) { int[] memory = new int[num.length]; Arrays.sort(num); ArrayList<ArrayList<Integer>> res = new ArrayList<>(); recall(num, memory, res, new Stack<Integer>()); return res; } public void recall(int[] num, int[] memory, ArrayList<ArrayList<Integer>> res, Stack<Integer> stack) { if (stack.size() == num.length) { res.add(new ArrayList<Integer>(stack)); return; } for (int i = 0;i < num.length;i++) { if (memory[i] != 0 || i > 0 && num[i] == num[i-1] && memory[i-1] == 0) { continue; } stack.push(num[i]); memory[i] = 1; recall(num, memory, res, stack); memory[i] = 0; stack.pop(); } } }
//有重复数字,意味着有重复的组合,去重首先想到的方法是用set处理 //C++ STL中的set是有序的,迭代器输出的时候是按照字典顺序的,这样省去了排序操作
class Solution {
private:
set<vector<int> > st;
public:
void DFS(vector<int> &num,int start){
if(start==num.size()){
st.insert(num);
return;
}
for(int i=start;i<num.size();i++){
swap(num[i],num[start]);
DFS(num,start+1);
swap(num[i],num[start]);
}
}
vector<vector<int> > permuteUnique(vector<int> &num) {
vector<vector<int> > res;
if(num.size()==0)
return res;
int start=0;
DFS(num,start);
set<vector<int> >::iterator it;
for(it=st.begin();it!=st.end();it++)
res.push_back(*it);
return res;
}
};
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& num) {
sort(num.begin(),num.end());
vector<vector<int>> res;
vector<int> temp;
vector<int>rec(num.size(),0);
backtracking(res,temp,num,rec);
return res;
}
void backtracking(vector<vector<int>>&res,vector<int>&temp,vector<int>num,vector<int>rec){
if(temp.size()==num.size()){
res.push_back(temp);
return ;
}
for(int i=0;i<num.size();i++){
if(rec[i]==0){//rec数组记录某个元素是否使用过
temp.push_back(num[i]);
rec[i]=1;
backtracking(res,temp,num,rec);
temp.pop_back();
rec[i]=0;
while((i+1)<num.size() && num[i]==num[i+1] )
i++; //确保相同元素只使用一次
}
}
}
};
class Solution {
public:
vector<vector<int> > permuteUnique(vector<int> &num) {
vector<vector<int> > res;
permutation(res,num,0);
return res;
}
void permutation(vector<vector<int> > &res,vector<int> &num,int s) {
if(s == num.size()-1&&Isunique(res,num))
res.push_back(num);
else{
for(int i=s;i<num.size();i++){
if(num[s]!=num[i]){
swap(num[s],num[i]);
permutation(res,num,s+1);
swap(num[s],num[i]);
}
else permutation(res,num,s+1);
}
}
}
private:
bool Isunique(vector<vector<int>> &res, vector<int> &num) {
for (int i = 0; i<res.size(); i++) {
if (num == res[i]) return false;
}
return true;
}
};
//1.题目说的numbers原来是-9到9的区间。。。 //2.为了保证不重复,可以考虑:从左往右枚举放置的每一位,然后对于枚举的该位,再从-9 //到9枚举应该放置在这位上的数 class Solution { public: int a[20]; vector<vector<int> > permuteUnique(vector<int> &num) { memset(a,0,sizeof(a)); for(auto v:num) a[v+9]++; vector<vector<int> > ans; vector<int> tmp; dfs(tmp,ans,0,num.size()); return ans; } void dfs(vector<int>&tmp,vector<vector<int> >&ans,int k,int sz){ if(k==sz) {ans.push_back(tmp);return;} for(int i=0;i<19;i++) if(a[i]>0){ a[i]--; tmp.push_back(i-9); dfs(tmp,ans,k+1,sz); tmp.pop_back(); a[i]++; } } };
class Solution { public: bool nextPermute(vector<int>& nums){ int n = nums.size() - 2; while(n >= 0 && nums[n] >= nums[n + 1]){ n--; } int j = nums.size() - 1; while(n >= 0 && nums[j] <= nums[n]){ j--; } if(n >= 0){ swap(nums[j],nums[n]); sort(nums.begin() + n + 1,nums.end()); return true; } return false; } vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> vcc; sort(nums.begin(),nums.end()); do{ vcc.push_back(nums); }while(nextPermute(nums)); return vcc; } };
class Solution { vector<int> d; set<vector<int> > z; vector<vector<int> > daan; int book[10000]={0}; public: vector<vector<int> > permuteUnique(vector<int> &num) { dfs(0,num); set<vector<int> >::iterator it; for(it=z.begin();it!=z.end();daan.push_back(*it),it++); return daan; } void dfs(int step,vector<int> &num) { int i; if(step==num.size()) z.insert(d); else { for(i=0;i<num.size();i++) if(book[i]==0) { book[i]=1; d.push_back(num[i]); dfs(step+1,num); book[i]=0; d.pop_back(); } } } };
class Solution { int a[19] = {0}; void permutation(vector<vector<int> > &result, vector<int> &num,int k,int n) { if(k == n) result.push_back(num); else{ for(int i=0;i<19;i++) { if(a[i] > 0) { a[i]--; num[k] = i-9; permutation(result,num,k+1,n); a[i]++; } } } } public: vector<vector<int> > permuteUnique(vector<int> &num) { int n = num.size(); for(int i=0;i<num.size();i++) a[num[i]+9]++; vector<vector<int> > result; permutation(result,num,0,n); return result; } };
class Solution { public: void dfs(vector<int> &num,vector<vector<int>> &res,vector<bool> visited,vector<int> &temp) { if(temp.size() == num.size()) { res.push_back(temp); return; } for(int i=0;i<num.size();i++) { if(i>0 && num[i]==num[i-1] && visited[i-1]) continue; if(!visited[i]) { visited[i] = 1; temp.push_back(num[i]); dfs(num,res,visited,temp); temp.pop_back(); visited[i] = 0; } } } vector<vector<int> > permuteUnique(vector<int> &num) { int len = num.size(); if(len==0) return vector<vector<int>> (); vector<vector<int>> res; vector<bool> visited(len,0); vector<int> temp; sort(num.begin(),num.end()); dfs(num,res,visited,temp); return res; } };
import java.util.*; public class Solution { //感觉很多人都没说明,回溯思想的核心,就是dfs,也就是helper中的for循环,每次都有nums. //nums.length次选择,但是这时候脑海中有一张树状图的网,唯一不同的是很多时候 //回溯会剪枝,比如used的设置,这样时间复杂度又n^n变为n!。 //回到本题,中的特殊情况,这里由于重复原因,只能选择树状图的一个方向,也就是排序后的 //顺序方向,唯一的 ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>(); public ArrayList<ArrayList<Integer>> permuteUnique(int[] nums) { ArrayList<Integer> list=new ArrayList<Integer>(); Arrays.sort(nums);//进行排序之后,重复的元素只能从一个方向进行拿,所以可以保证不重复 helper(list,nums,new boolean[nums.length]); return res; } public void helper(ArrayList<Integer> list,int []nums,boolean []used){ if(list.size()==nums.length){ res.add(new ArrayList<Integer>(list)); return; } for(int i=0;i<nums.length;i++ ){ if(used[i]==true) continue; if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;//只能按一个顺序进行访问连续相同的元素,才能保证唯一 used[i]=true; list.add(nums[i]); helper(list,nums,used); list.remove(list.size()-1); used[i]=false; } } }
import java.util.*; /** * 47. Permutations II * * @author Jacob * 思路:与46. Permutations解法类似。区别是,该题需要单独建立一个boolean数组 * 用来记录nums中的元素是否被使用(是否已经加入list集合) */ public class Solution { ArrayList<ArrayList<Integer>> res; public ArrayList<ArrayList<Integer>> permuteUnique(int[] nums) { res = new ArrayList<ArrayList<Integer>>(); if (nums == null || nums.length < 1) return res; Arrays.sort(nums); ArrayList<Integer> list = new ArrayList<Integer>(); boolean[] used = new boolean[nums.length]; solve(list, nums, used); return res; } private void solve(ArrayList<Integer> list, int[] nums, boolean[] used) { if (list.size() == nums.length) { res.add(new ArrayList<Integer>(list)); return; } for (int i = 0; i < nums.length; i++) { if (used[i]) continue; /* * 只需要判断i和i-1(而不需要判断i与i-2...) 相同的元素一定是相邻的。 * 如果i-2,i-1,i相同,那么在上一轮循环就已经判断了i-1,i,本轮循环不需要重复判断 */ if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; list.add(nums[i]); used[i]=true; solve(list, nums, used); used[i]=false; list.remove(list.size()-1); } } }
class Solution { int array[19] = {0};// 统计0~9,10个数字出现次数 void permutation(vector<vector<int> >& ans,vector<int> &num,int k,int n) { if(k==n) ans.push_back(num); else { for(int i=0;i<19;i++) { if(array[i] >0) { array[i]--; num[k]=i-9; permutation(ans,num,k+1,n); array[i]++; } } } } public: vector<vector<int> > permuteUnique(vector<int> &num) { for(int i=0;i<num.size();i++) array[num[i]+9]++; vector<vector<int> > ans; permutation(ans,num,0,num.size()); return ans; } };
class Solution { public: vector<vector<int> > permuteUnique(vector<int> &num) { // 时间复杂度O(N!),空间复杂度O(N!) vector<vector<int>> res; vector<int> path; sort(num.begin(), num.end()); recursion(num, path, res); return res; } void recursion(vector<int> &num, vector<int> &path, vector<vector<int>> &res) { if (num.empty()) { res.push_back(path); return; } unordered_set<int> set; for (int i = 0; i < num.size(); ++i) { if (set.find(num[i]) != set.end()) continue; set.insert(num[i]); path.push_back(num[i]); vector<int> tmp(num); tmp.erase(tmp.begin() + i); recursion(tmp, path, res); path.pop_back(); } } };