首页 > 代码库 > Permutations II leetcode java

Permutations II leetcode java

2024-07-16 09:31:36   217人阅读

题目：

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], and [2,1,1].

 

题解：

 这道题跟Permutaitons没啥大的区别，就是结果去重。

 我之前也有写过去重的两个方法:

 一个是在加入结果的时候用contains判断，一个是在找结果的时候看他是不是跟前一个元素相同。

 这道题还要考虑的是visited情况，前一个元素就算跟当前元素相同，如果visited==true也没关系。但是如果前面元素跟当前元素相同还没被visited，那么就要做去重处理了。

 

代码如下：

 1     public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
 2         ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
 3         ArrayList<Integer> item = new ArrayList<Integer>();
 4         
 5         if(num.length==0||num==null)
 6             return res;
 7         boolean[] visited = new boolean[num.length];  
 8         Arrays.sort(num);
 9         permutation_helper(num,res,item,visited);
10         return res;
11     }
12     
13     public void permutation_helper(int[] num, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> item,boolean[] visited){
14         if(item.size()==num.length){
15             res.add(new ArrayList<Integer>(item));
16             return;
17         }
18         
19         for(int i = 0; i<num.length;i++){
20             if(i>0 && num[i-1] == num[i] && !visited[i-1])
21                 continue;
22             if(!visited[i]){
23                 item.add(num[i]);
24                 visited[i]=true;
25                 permutation_helper(num,res,item,visited);
26                 item.remove(item.size()-1);
27                 visited[i]=false;
28             }
29         }
30     }

 


联系
我们