给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。
数据范围： 
，数组中的值满足 
要求：空间复杂度 )
，时间复杂度
[编程题]有重复项数字的全排列
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);
}
}
}
发表于 2021-12-12 08:52:30
回复(0)
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);
}
}
}
}
发表于 2021-10-03 09:37:22
回复(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;
}
}
}
发表于 2021-07-02 10:17:29
回复(0)
每个位置选择和后面一个数交换位置（也可以和自己交换，就是保持原值不变），使得每种不同的数字都能够在该位置出现一次，如此递归下去形成各种组合。为防止相同的数字重复出现在该位置，需要使用set判重。
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]); //复原
}
}
};
发表于 2021-04-21 16:02:13
回复(0)
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();
}
}
}
发表于 2021-01-12 16:45:11
回复(0)
//有重复数字，意味着有重复的组合，去重首先想到的方法是用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;
}
};
发表于 2018-08-29 10:57:18
回复(1)
c++ version.回溯求出所有情况，与permutation1不同的是，这个要用数组来记录某个元素是否用过。
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++; //确保相同元素只使用一次
}
}
}
};
编辑于 2018-09-01 14:58:19
回复(3)
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;
}
};
发表于 2018-05-08 15:28:35
回复(1)
//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]++;
}
}
};
发表于 2017-08-10 10:16:53
回复(0)
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;
}
};
发表于 2017-07-09 14:56:21
回复(1)
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;
}
};
发表于 2017-08-26 01:50:06
回复(0)
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;
}
};
发表于 2017-07-14 15:51:00
回复(0)
/*
C++ 解题思路
1. 解决重复数字问题
先对容器num进行排序，保证重复数字相邻，这样在后续操作中，利用条件，若后一数与前一数相等，则不处理
2、解决数字是否进入排列list容器问题
使用额外bool类型容器used，区分当前值是否已进入排列当中
3、解决排列问题
（1）若list长度等于num，则压入容器res
（2）对容器num进行for循环
边界条件：
若当前值已使用过，不处理；
若当前值与前一值相等，且前一值未使用过，不处理
（举例：112，循环第一个1作第一位时，第二位是第二个1，会被记录，但是循环第二个1做第一位时，第二位是第一个1，就不会被记录，避免重复）
当前值压入并依次作为排列list的元素，将used容器对应位置true
将当前list、num、used和res送入排列函数，进行递归
将used中对应位置false，list弹出当前值，继续for循环
*/
class Solution {
public:
vector<vector<int> > permuteUnique(vector<int> &num) {
vector<vector<int>> res;
if (num.size() == 0)
return res;
sort(num.begin(), num.end());
vector<bool> used(num.size());
vector<int> list;
permute(num, used, list, res);
return res;
}
void permute(vector<int>& num, vector<bool>& used, vector<int>& list, vector<vector<int>>& res) {
if (list.size() == num.size()) {
res.push_back(list);
return;
}
for (int i = 0; i < num.size(); i++) {
if (used[i])
continue;
if (i > 0 && num[i - 1] == num[i] && !used[i - 1])
continue;
used[i] = true;
list.push_back(num[i]);
permute(num, used, list, res);
used[i] = false;
list.pop_back();
}
}
};
发表于 2018-07-01 22:43:09
回复(0)
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;
}
}
}
编辑于 2017-11-08 10:57:30
回复(5)
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);
}
}
}
发表于 2017-08-19 11:08:39
回复(0)
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]);
}
}
};
发表于 2017-09-11 19:56:52
回复(1)
// 回溯
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; // 回溯
}
}
};
编辑于 2019-08-14 15:58:49
回复(0)
特异全排列，候选为-9~9,19个数字
使用array[19]记录着19个数字在序列中出现的次数
条件
：
array
中记录
i, array[i]>0
，就是原始序列中的这个字母还没有被用完
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;
}
};
发表于 2016-09-02 17:37:33
回复(0)
这题直接在上一题基础改就行了，对于重复的数字不递归就行了。但是由于上题学的官方代码是错的，因而让我调试了很久。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param num int整型vector
* @return int整型vector<vector<>>
*/
void recursion(vector<vector<int> >& res, vector<int>& num, int index) {
if (index == num.size() - 1) {
res.push_back(num);
} else {
int tage = num[index];//保存用过的数
for (int i = index; i < num.size(); i++) {
if (num[i] == tage && index != i) continue;
tage = num[i];
vector<int> num1 = num;
swap(num[index], num[i]);
sort(num.begin() + index + 1, num.end());
recursion(res, num, index + 1);
num = num1;
}
}
}
vector<vector<int> > permuteUnique(vector<int>& num) {
// write code here
sort(num.begin(), num.end());
vector<vector<int> > res;
recursion(res, num, 0);
return res;
}
};
发表于 2024-06-18 22:04:50
回复(0)
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();
}
}
};
发表于 2022-10-14 21:28:23
回复(2)
问题信息
通过挑战的用户
查看代码-
2022-11-15 14:45:08 -
2022-10-22 14:49:11
-
2022-10-13 22:13:58 -
2022-09-23 14:30:53
-
2022-09-20 16:37:23
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
