本文共 2370 字，大约阅读时间需要 7 分钟。

LeetCode第47题思悟—— 全排列 II（permutations-ii）

知识点预告

1. 深度优先搜索；
2. 数据去重；

题目要求

给定一个可包含重复数字的序列，返回所有不重复的全排列。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/permutations-ii

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例

输入: [1,1,2]

输出:

[

[1,1,2],

[1,2,1],

[2,1,1]

]

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/permutations-ii

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的思路

public List
   
    
     > permute(int[] nums) {
   	Arrays.sort(nums);	List
     
      
       > results=new ArrayList<>();	if(nums.length==0){
   		return results;	}	boolean[] books=new boolean[nums.length];	List
       
         start;	List
        
         
          > startList=new ArrayList<>(); int lastNum; for(int i=0;i
          
           (nums.length); start.add(nums[i]); startList.add(start); books[i] = true; results.addAll(stepForward(nums, books, startList, nums.length - 1)); books[i] = false; startList.remove(start); lastNum=nums[i]; i++; while(i
           
            > stepForward(int[]nums,boolean[] books, List
            
             
              > products,int needNum){ if(needNum==0){ return products; } int restNum=needNum; List
              
               
                >nextToFill=products; List
                
                 
                  >currentToFill; List
                  
                   
                    >result=new ArrayList<>(); int lastNum=nums[0]; for(int i=0;i
                    
                      0) { nextToFill = new ArrayList<>(currentToFill.size()); for (List
                     
                       list : currentToFill) { nextToFill.add(new ArrayList<>(list)); list.add(nums[i]); } } else { for (List
                      
                        list : currentToFill) { list.add(nums[i]); } } result.addAll(stepForward(nums, books, currentToFill, needNum - 1)); books[i] = false; lastNum=nums[i]; i++; while(i
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

优秀解法

public List
   
    
     > permuteUnique(int[] nums) {
   	List
     
      
       > permutes = new ArrayList<>();	List
       
         permuteList = new ArrayList<>();	Arrays.sort(nums);	boolean[] hasVisited = new boolean[nums.length];	dfs(permuteList, permutes, hasVisited, nums);	return permutes;}private void dfs(List
        
          permuteList, List
         
          
           > permutes, boolean[] visited, final int[] nums) { if(permuteList.size() == nums.length) { permutes.add(new ArrayList<>(permuteList)); return; } for (int i = 0; i < visited.length; i++) { if (i != 0 && nums[i] == nums[i - 1] && !visited[i - 1]) { continue; } if (visited[i]) { continue; } visited[i] = true; permuteList.add(nums[i]); dfs(permuteList, permutes, visited, nums); permuteList.remove(permuteList.size() - 1); visited[i] = false; }}
          
         
        
       
      
     
    
   

差异分析

自己解法所存在的问题还是同上一题一样，中间数据的复制操作过于频繁；该题的解法是深度优先搜索；

知识点小结

1. 深度优先搜索；
2. 数据去重；