文档章节

全排列(去除重复)Permutations II

叶枫啦啦
 叶枫啦啦
发布于 2017/09/04 16:44
字数 966
阅读 10
收藏 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]
]

解决:

① 与Permutations类似,因为包含重复的数字,所以我们要对重复的排列序列进行排除,首先我们对数组进行排序,判断当前遍历到的数是否与前一个数相同,使用一个标记数组boolean[] used来判断前一个相同的值是否被使用了,若正在被使用,说明正在处于前一个值得递归过程中,当前值不能被跳过;若没有被使用,说明这个值已经作为头部被使用过了,跳过当前值以排除重复。使用一个链表pre来记录之前排列好的值,需要注意的是,遍历完成一个排列之后,需要还原pre以进行下一次排列

public class Solution { //7ms
    public List<List<Integer>> permuteUnique(int[] nums) {   
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(nums == null || nums.length == 0) return res;
        boolean [] used = new boolean[nums.length];
        List<Integer> pre = new ArrayList<>();
        Arrays.sort(nums);
        dfs(nums,used,pre, res);
        return res;
    }
    private void dfs(int[] nums, boolean [] used, List<Integer> pre, List<List<Integer>> res){
        if(pre.size() == nums.length){
            res.add(new ArrayList<>(pre));//若直接res.add(pre),会导致集合为空[[],[],[],[],[],[]]
            return;
        }
        for(int i = 0; i < nums.length; i ++){
            if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;//去重
            if(! used[i]){
                used[i] = true;
                pre.add(nums[i]);//加入当前值
                dfs(nums,used,pre,res);//递归查找值
                pre.remove(pre.size() - 1);//还原前一个排列,继续查找排列
                used[i] = false;
            }
        }
    }
}

② 另外,我们可以使用一个临时链表cur来记录加入当前值之后的排列,这样,就可以避免还原pre。

public class Solution { //11ms
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        int len = nums.length;
        if(len == 0) return res;
        Arrays.sort(nums);
        boolean[] used = new boolean[len];
        List<Integer> pre = new ArrayList<>();
        dfs(nums,used,pre);
        return res;
    }
    private void dfs(int[] nums,boolean[] used,List<Integer> pre){
        if(pre.size() == nums.length){//完成一个排列
            //res.add(new ArrayList<Integer>(pre));
            res.add(pre);

            return;
        }
        for(int i = 0;i < nums.length;i ++){
            if(i > 0 && nums[i] == nums[i - 1] && ! used[i - 1]) continue;//前一个数没有被选中,说明在前一个数时已经完成了以该数为开头的排列
            List<Integer> cur = new ArrayList<Integer>(pre);//这样就不需要还原pre了,因为pre与cur分开了
            if(! used[i]){
                cur.add(nums[i]);
                used[i] = true;
                dfs(nums,used,cur);
                used[i] = false;
            }
        }
    }
}

③ 直接使用backtrack(DFS)而不用使用标记位。并且不需要对数组排序。以{1,1,2}为例进行递归分析如下:

class Solution { //6ms
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(nums,0,res);
        return res;
    }
    public void dfs(int[] nums,int i,List<List<Integer>> res){//i表示当前排列的开头在原固定数组中的位置
        //找到转换完成的链表,将其存入链表中
        if(i == nums.length - 1){//递归结束条件,得到一个排列
            List<Integer> tmp = new ArrayList<>();
            for (int j = 0;j < nums.length ;j ++ ) {
                tmp.add(nums[j]);
            }
            res.add(tmp);
        }else{//没有完成排列
            for (int j = i;j < nums.length ;j ++ ){//排列i之后的数
                if(containsRepeated(nums,i,j)) continue;//判断i到j之间是否存在重复,如果存在,则不需要交换和递归,因为这是同一个排列  
                //若不存在重复,则进行以下排列              
                swap(nums,i,j); //交换开头,若j=i表示固定当前开头计算排列,否则表示以当前值为开头的已经排列完了
                dfs(nums,i + 1,res);//改变数组的开头为原数组中i之后的第一个数,递归得到它的全排列
                swap(nums,i,j);//递归完成,还原交换的数组
            }
        }
    }
    public boolean containsRepeated(int[] nums,int i,int j){
        for (int k = i;k <= j - 1 ;k ++ ) {//若i=j,则无法进入该循环,直接返回false;
            if(nums[k] == nums[j]) return true;
        }
        return false;
    }
    public void swap(int[] nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

© 著作权归作者所有

叶枫啦啦
粉丝 14
博文 583
码字总数 400448
作品 0
海淀
私信 提问
47. Permutations II

使用递归算法特性:必须的终止条件子问题比原来的问题小子问题可以再递归求解子问题的解能够组成大问题的解 a bc b ac c ba

datacube
2016/07/05
5
0
leetcode permutation/combination

Next Permutation 将整个排列看成是一个数,按该数大小,从小到大排列,求当前排列的下一个排列 // ①从右到左找到第一个非递增的位置 pivot// ②从右到左找到第一个大于 *pivot 的位置 chan...

matrixz
2014/09/07
41
0
确定某字符串的所有排列组合

/** * 功能:确定某字符串的所有排列组合。 / 注意:不考虑重复字符。若考虑重复字符,只需在加入permulations时去掉重复的字符串即可。 [java] view plain copy /* * 思路:元素由少到多,将...

一贱书生
2016/11/22
104
0
Lintcode16 Permutations II solution 题解

【题目描述】 Given a list of numbers with duplicate number in it. Find all unique permutations. 给出一个具有重复数字的列表,找出列表所有不同的排列。 【题目链接】 http://www.lin...

coderer
2017/04/27
0
0
LeetCode 分类刷题—— Backtracking

Backtracking 的 Tips: 排列问题 Permutations。第 46 题,第 47 题。第 60 题,第 526 题,第 996 题。 组合问题 Combination。第 39 题,第 40 题,第 77 题,第 216 题。 排列和组合杂交问...

一缕殇流化隐半边冰霜
07/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Handler简解

Handler 这里简化一下代码 以便理解 Handler不一定要在主线程建 但如Handler handler = new Handler(); 会使用当前的Looper的, 由于要更新UI 所以最好在主线程 new Handler() { mLooper = Lo...

shzwork
9分钟前
1
0
h5获取摄像头拍照功能

完整代码展示: <!DOCTYPE html> <head> <title>HTML5 GetUserMedia Demo</title> <meta charset="utf-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum......

诗书易经
11分钟前
1
0
正向代理和反向代理

文章来源 运维公会:正向代理和反向代理 1、正向代理 (1)服务对象不同 正向代理服务器的服务对象是客户端,可以将客户端和代理服务器看作一个整体。 (2)配置方法不同 需要在客户端配置代...

运维团
28分钟前
2
0
5个避免意外论文重复率高的方法

即使你不是故意抄袭,但你可能在无意中抄袭了别人的论文, 这个叫做意外抄袭,它可能正发生在你身上,如果你不熟悉学术 道德规范,这里将告诉你5个基本的方法来避免意外抄袭。 Tip1 熟悉其他...

论文辅导员
29分钟前
2
0
Maven通过profiles标签读取不同的配置

<profiles> <profile> <id>dev</id> <properties> <profiles.active>dev</profiles.active> </properties> ......

时刻在奔跑
35分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部