首页 > 试题广场 >

有重复项数字的全排列

[编程题]有重复项数字的全排列
  • 热度指数:91286 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给出一组可能包含重复项的数字,返回该组数字的所有排列。结果以字典序升序排列。

数据范围: ,数组中的值满足
要求:空间复杂度 ,时间复杂度
示例1

输入

[1,1,2]

输出

[[1,1,2],[1,2,1],[2,1,1]]
示例2

输入

[0,1]

输出

[[0,1],[1,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)
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 {
    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();
            	}
        }
    }
};

发表于 2016-08-16 19:23:07 回复(0)
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)
特异全排列,候选为-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:
    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)