题目大意

给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例：
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

分析

这个题只要在全排列I的基础上加一个去重操作，而这个去重操作需要注意效率。可以用Set去重，但是效率较低；可以在permutation的时候加入判断，直接去掉造成重复的交换。

代码一：Set去重

    List<Integer> path = new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        if(nums==null || nums.length == 0) return res;
        permuteCore(nums,0);
        res = removeDup(res);
        return res;
    }

    private void permuteCore(int[] nums, int pos) {
        if(pos == nums.length-1) {
            for(int i=0;i<nums.length;i++)
                path.add(nums[i]);
            res.add(path);
            path = new ArrayList<>();
            //path.clear();
            return;
        } else {
            for(int i=pos;i<nums.length;i++) {
                swap(nums,pos,i);
                permuteCore(nums,pos+1);
                swap(nums,pos,i);
            }
        }
    }

    private void swap(int[] nums, int i,int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    private List<List<Integer>> removeDup(List<List<Integer>> list) {
        //给list去重
        HashSet<List<Integer>> set = new HashSet<>();
        List<List<Integer>> r = new ArrayList<>();
        for(int i=0;i<list.size();i++) {
            if(set.add(list.get(i)))
                r.add(list.get(i));
        }
        return r;
    }

运行时间39ms,击败17.82%.

代码二：判断条件

    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        if(nums==null || nums.length == 0) return res;
        permuteCore(nums,0);
        return res;
    }
    
    private void permuteCore(int[] nums, int pos) {
        if(pos == nums.length-1) {
            List<Integer> path = new ArrayList<>();
            for(int i=0;i<nums.length;i++)
                path.add(nums[i]);
            res.add(path);
            return;
        } else {
            for(int i=pos;i<nums.length;i++) {
                if(canSwap(nums,pos,i)) {
                    swap(nums,pos,i);
                    permuteCore(nums,pos+1);
                    swap(nums,pos,i);
                }
            }
        }
    }

    private boolean canSwap(int[] nums, int i, int j) {
        for(int k=i;k<j;k++) {
            if(nums[k] == nums[j])
                return false;
        }
        return true;
    }

    private void swap(int[] nums, int i,int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

运行时间1ms,击败100%。