leetcode 47. Permutations II 全排列问题（去掉重复元素）+递归

野性酷女 2022-06-09 10:19 233阅读 0赞

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

这道题考察的也是全排列，不过和上一道题不同的是，本题可能存在重复的元素，这里要避免重复的元素出现，主要避免重复的递归入口即可。

代码如下：

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class Solution 
    {
        
        // http://blog.csdn.net/chenchaofuck1/article/details/51194976  
        // 这个链接上的代码有点问题，不过算法没问题
    
        //排列问题，按照排列思想，遍历每个位置，对每个位置每次都从集合中选一个未被选的元素。
        //所以排列个数为n!，时间复杂度为n！。 
        //对传来的数组利用交换，每次把选择的元素交换到该位置上，
        //再递归后面位置。对于题2有重复元素，要避免交换重复的，所以判断如果出现过就不再交换。
    
    
        // 这个和一半的全排列的区别就是去掉重复元素的swap
        public List<List<Integer>> permuteUnique(int[] nums) 
        {
            //特殊情况
            List<List<Integer>> res=new ArrayList<>();
            if(nums==null || nums.length<=0)
                return res;
    
            //排序不是必须的，不过我喜欢排好序的数组
            Arrays.sort(nums);
            //就是一个全排列问题
            fullPermute(res,nums,0,nums.length);
            return res;
        }
    
        private void fullPermute(List<List<Integer>> res, int[] nums, int beg, int length)
        {
            if(beg==length)
            {
                List<Integer> tt=new ArrayList<>();
                for(int j=0;j<length;j++)
                    tt.add(nums[j]);
                res.add(tt);
            }else
            {
                for(int j=beg;j<length;j++)
                {   
                    //这个主要是为了去处重复元素
                    boolean flag=false;
                    //k==beg 这个刚好跳过，主要是找beg到j的重复元素
                    for(int k=beg;k<j;k++)
                    {
                        if(nums[k]==nums[j])
                        {
                            flag=true;
                            break;
                        }
                    }
                    //发现重复元素就跳过
                    if(flag)
                        continue;
    
                    int tmp=nums[beg];
                    nums[beg]=nums[j];
                    nums[j]=tmp;
    
                    fullPermute(res, nums, beg+1, length);
    
                    tmp=nums[beg];
                    nums[beg]=nums[j];
                    nums[j]=tmp;
                }
            }
    
        }
    }

下面是C++的做法，就是做一下剪枝

代码如下：

#include <iostream>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    class Solution 
    {
    public:
        vector<vector<int>> res;
        vector<vector<int>> permuteUnique(vector<int>& nums)
        {
            if (nums.size() <= 1)
            {
                res.push_back(nums);
                return res;
            }
    
            sort(nums.begin(),nums.end());
            getAll(nums, 0);
            return res;
        }
    
        void getAll(vector<int>& nums, int beg)
        {
            if (beg == nums.size())
            {
                res.push_back(nums);
                return;
            }
            else
            {
                for (int i = beg; i < nums.size(); i++)
                {
                    //这个主要是为了去处重复元素
                    bool flag = false;
                    //k==beg 这个刚好跳过，主要是找beg到j的重复元素
                    for (int k = beg; k<i; k++)
                    {
                        if (nums[k] == nums[i])
                        {
                            flag = true;
                            break;
                        }
                    }
                    //发现重复元素就跳过
                    if (flag)
                        continue;
    
                    int tmp = nums[beg];
                    nums[beg] = nums[i];
                    nums[i] = tmp;
    
                    getAll(nums, beg + 1);
    
                    tmp = nums[beg];
                    nums[beg] = nums[i];
                    nums[i] = tmp;
                }
            }
        }
    };