题目描述

给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。

数据范围： $0 < n \le 8$ ，数组中的值满足 $-1 \le val \le 5$

题目分析

题目时在NC43 “没有重复项数字的所有排列” 基础上增加了有重复数字这个条件，因为有重复数字，排列的n!种情况也会有重复的排列，直观地想，可以在排列结果中，若是遇到相同的排列，则不加入结果中，如图：

alt

在判断是否已经存在排列时，需要对已有的排列都遍历一遍，时间复杂度为 $O (n^{2})$ ，而这个判断判断是在dfs方法中的，dfs遍历所有的情况时间复杂度为 $O (n!)$ ，这样总的时间复杂度为 $O (n! n^{2})$ ，其实可以直接在dfs过程中直接排除重复的情况，避免很多不必要的判断，主要判断方式为：当碰到相同的数时，可以从前面的数往后遍历（先将前面的加入排列中），若是前面的数还没有访问过，则说明是从后面的数开始，但因为数字相同，所以必然产生重复的排列，所以可以直接跳过。

解题思路

方法1：dfs递归回溯，使用set记录位置数字是否被访问过

在判断数字是否被访问时，可以使用set来保存访问过的数字，后面在选择时，要在判断set是否包含之上加如下判断：

if(i>0 && num[i] == num[i-1] && !set.contains(i-1)){}

主要是在遇到相同数字时，前面没有访问过但直接访问的后面数字，判断为重复排列。

方法2：dfs递归回溯，使用下标数组标记

因为题目说明了数据的范围数组长度0~8，可以提前设置长度为9的flag数组，来标记下标位置的数据是否被访问。判断是否重复的方式与方法1相同。

代码实现

方法1：dfs递归回溯，使用set记录位置数字是否被访问过

    ArrayList<ArrayList<Integer>> res;
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        Arrays.sort(num);
        res = new ArrayList<>();
        HashSet<Integer> set = new HashSet<>();
        dfs(num, 0, set, new ArrayList<Integer>());
        return res;
    }
     
    public void dfs(int[] num, int start, HashSet<Integer> set, ArrayList<Integer> path){
        if(path.size() == num.length){
            // 枚举了所有数后，将该结果保存
            res.add(new ArrayList<Integer>(path));
            return;
        }
        for(int i=0;i<num.length;i++){
            // 若是已经存储该数字（下标），或者重复的数字中前一个数字没有访问过（说明是以后面为开始访问到前面的数是重复情况）
            if(set.contains(i) || (i>0 && num[i] == num[i-1] && !set.contains(i-1))){
                continue;
            }
            // 选择数字
            set.add(i);
            path.add(num[i]);
            dfs(num, i+1, set, path);
            // 撤销选择
            set.remove(i);
            path.remove(path.size()-1);
        }
    }

时间复杂度： $O (n n!)$ ，对于数字的排列情况一共有n!种，而在挑选数字的方法中需要对n个数字依次进行遍历，所以时间复杂度为 $O (n n!)$ ；

空间复杂度： $O (n)$ ，在遍历的过程中需要使用额外的set来存储数字下标，最多存储n个数字，同时还需要使用n大小的递归栈空间。

方法2：dfs递归回溯，使用下标数组

    ArrayList<ArrayList<Integer>> res;
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        Arrays.sort(num);
        res = new ArrayList<>();
        // 使用数组来记录访问的数组下标
        boolean[] flag = new boolean[9];
        dfs(num, 0, flag, new ArrayList<Integer>());
        return res;
    }
      
    public void dfs(int[] num, int start, boolean[] flag, ArrayList<Integer> path){
        if(path.size() == num.length){
            // 枚举了所有数后，将该结果保存
            res.add(new ArrayList<Integer>(path));
            return;
        }
        for(int i=0;i<num.length;i++){
            // 若是已经存储该数字（下标），或者重复的数字中前一个数字没有访问过（说明是以后面为开始访问到前面的数是重复情况）
            if(flag[i] || (i>0 && num[i] == num[i-1] && flag[i-1])){
                continue;
            }
            // 选择数字下标
            flag[i] = true;
            path.add(num[i]);
            dfs(num, i+1, flag, path);
            // 撤销选择
            flag[i] = false;
            path.remove(path.size()-1);
        }
    }

时间复杂度： $O (n n!)$ ，同方法1；

空间复杂度： $O (n)$ ，使用了标记数组代替set，在数据空间上使用了O(1)的空间，但递归栈仍需要n的空间。

题解 | NC42 #有重复项数字的所有排列#

题目描述

题目分析

解题思路

代码实现