LeetCode_数组_中等_47.全排列II

迈不过友情╰ 2023-10-06 18:57 43阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现(Java）

## 1.题目 ##

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

示例 1：  
输入：nums = \[1,1,2\]  
输出：  
\[\[1,1,2\],  
\[1,2,1\],  
\[2,1,1\]\]

示例 2：  
输入：nums = \[1,2,3\]  
输出：\[\[1,2,3\],\[1,3,2\],\[2,1,3\],\[2,3,1\],\[3,1,2\],\[3,2,1\]\]

提示：  
1 <= nums.length <= 8  
\-10 <= nums\[i\] <= 10

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/permutations-ii

## 2.思路 ##

（1）在[46.全排列][46.]这题的基础上，保证加入res结果不是重复的代码即可，但是该方法需要花费大量的时间去判断结果是否重复，效率比较低，所以不推荐使用。解题的关键在于从根源上保证全排列不重复，而不是在排列之后去掉重复的结果。  
（2）来自[LeetCode本题官方题解][LeetCode]

## 3.代码实现(Java） ##

//（1）思路1
    class Solution {
        
    
        //保存结果
        List<List<Integer>> res=new ArrayList<List<Integer>>();
    
        public List<List<Integer>> permuteUnique(int[] nums) {
        
            int n=nums.length;
            List<Integer> listNums=new ArrayList<Integer>();
            for(int i=0;i<n;i++){
        
                listNums.add(nums[i]);
            }
            Permutation(listNums,0,n-1);
            return res;
        }
    
        //产生listNums[k:m]的所有排列
        public void Permutation(List<Integer> listNums,int k,int m){
        
            //只剩下一个元素，且需保证添加的结果不是重复的
            if(k==m && !res.contains(new ArrayList<Integer>(listNums))){
        
                /* 此处不能直接使用res.add(listNums)，因为添加的是listNums的引用地址，而这里的
                 * listNums是动态变化的，所以只有每次都新建一个list对象才能保存每次递归的结果
                */
                res.add(new ArrayList<Integer>(listNums));
            }else{
        
            	//还有多个元素待排列，递归产生排列
                for(int i=k;i<=m;i++){
        
                    Collections.swap(listNums,k,i);
                    Permutation(listNums,k+1,m);
                    Collections.swap(listNums,k,i);
                }
            }
        }
    }

//（2）来自LeetCode本题官方题解
    class Solution {
        
        boolean[] vis;
    
        public List<List<Integer>> permuteUnique(int[] nums) {
        
            List<List<Integer>> ans = new ArrayList<List<Integer>>();
            List<Integer> perm = new ArrayList<Integer>();
            vis = new boolean[nums.length];
            Arrays.sort(nums);
            backtrack(nums, ans, 0, perm);
            return ans;
        }
    
        public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
        
            if (idx == nums.length) {
        
                ans.add(new ArrayList<Integer>(perm));
                return;
            }
            for (int i = 0; i < nums.length; ++i) {
        
                if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
        
                    continue;
                }
                perm.add(nums[i]);
                vis[i] = true;
                backtrack(nums, ans, idx + 1, perm);
                vis[i] = false;
                perm.remove(idx);
            }
        }
    }

[46.]: https://blog.csdn.net/weixin_43004044/article/details/119631772
[LeetCode]: https://leetcode-cn.com/problems/permutations-ii/solution/quan-pai-lie-ii-by-leetcode-solution/