一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 456|回复: 10
收起左侧

[Leetcode] permutationII疑问

[复制链接] |试试Instant~ |关注本帖
zh355245849 发表于 2015-7-4 17:42:12 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
  1. public class Solution {
  2.     public List<List<Integer>> permuteUnique(int[] nums) {
  3.         List<List<Integer>> res = new ArrayList<List<Integer>>();
  4.         List<Integer> rows = new ArrayList<Integer>();
  5.         if(nums == null || nums.length == 0)
  6.             return res;
  7.         Arrays.sort(nums);
  8.         boolean[] record = new boolean[nums.length];
  9.         dfs(nums, record, res, rows);
  10.         return res;
  11.     }
  12.     public void dfs(int[] nums, boolean[] record, List<List<Integer>> res, List<Integer> rows) {
  13.         if(nums.length == rows.size()) {
  14.             if(!res.contains(rows))
  15.             res.add(new ArrayList<Integer>(rows));
  16.             return ;
  17.         }
  18.         for(int i = 0; i < nums.length; i++) {
  19.             //if(i > 0 && nums[i]==nums[i-1] && record[i - 1] == false)
  20.               //  continue;            
  21.             if(record[i] == false) {
  22.                 rows.add(nums[i]);
  23.                 record[i] = true;
  24.                 dfs(nums, record, res, rows);
  25.                 record[i] = false;
  26.                 rows.remove(rows.size() - 1);
  27.                 //while(i < nums.length - 1 && nums[i] == nums[i+1])
  28.                   //  i++;
  29.             }
  30.             
  31.         }
  32.         return ;
  33.     }
  34. }
复制代码
各路大神,我想问下这道题这样写为什么会超时。。。写subsetII时用contains明明是可以通过的,这里为什么不行了。。。谢谢了!
stellari 发表于 2015-7-4 18:07:32 | 显示全部楼层
本帖最后由 stellari 于 2015-7-4 18:11 编辑
zh355245849 发表于 2015-7-4 18:01
哦,也就是说用            if(!res.contains(rows))  来检查比下面的查重废很多时间是吗,因为把所有的 ...


可以这样理解。Backtracking中很重要的一步就是剪枝(pruning),也就是当发现当前这条路没有前途时,应该立刻放弃掉。而如果像原来的代码中那样,等于是放弃了剪枝。那么很多本来在看到第一个数字就能否决的伪solution,现在要将其的全部数字都处理一遍才能否决。如果数组中重复字符非常多,伪solution的个数可能会远超过真solution的个数。所以程序的实际运行时间将非常有可能达到该算法的时间复杂度的上限O(N!)。

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

stellari 发表于 2015-7-4 17:57:41 | 显示全部楼层

z

本帖最后由 stellari 于 2015-7-4 18:03 编辑

为什么把重复性检查的代码注释掉了?这题如果不检查重复性的话,如果遇到很长的重复字串,比如aaaaaaaaaaaaa.....b这样的测试用例时非常容易超时。至于为何Subset不会超时,这也不难理解。Subset的复杂度是O(N*2^N),Permutation的复杂度则是O(N*N!)。后者比前者要大的多。如果两题的测试用例长度差不多,那么完全有可能出现前者AC,后者TLE的情况。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| zh355245849 发表于 2015-7-4 18:01:17 | 显示全部楼层
stellari 发表于 2015-7-4 17:57
为什么把重复性检查的代码注释掉了?这题如果不检查重复性的话,如果遇到很长的重复字串,比如aaaaaaaaaaaa ...

哦,也就是说用            if(!res.contains(rows))  来检查比下面的查重废很多时间是吗,因为把所有的都执行了一遍?。。不知道我理解的对不对。。。
回复 支持 反对

使用道具 举报

水逼一枚 发表于 2015-7-5 05:04:34 | 显示全部楼层
zh355245849 发表于 2015-7-4 18:01
哦,也就是说用            if(!res.contains(rows))  来检查比下面的查重废很多时间是吗,因为把所有的 ...

你把解空间树的结构画出来你就知道了。如果你用hash去重,你实际上还是要去走一些重复的path后直到排列的数字个数到位时再去hash判断。而我们说剪枝是你在探索某个child nodes时发现,如果从这个child node探索下去和之前的child node探索下去的结果重复的,那么立马剪枝掉。相当于后者避免了那些重复的运算和探索过程,而前者还是要去探索直到递归终止时才判断是否重复,那么这之间消耗的时间对于一些比较特殊的test case的时候就容易TLE

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

glaciersilent 发表于 2015-7-5 05:26:51 | 显示全部楼层
我认为这题的testcase或者benchmark后来有修改 我早先也是Backtrack做是可以AC的,前两天做就不行了,包括之前可以AC的都不行了,后来优化了半天怎么都不行。后来看了看discuss, 现在比较好的方法是用next permutation那题的算法。先从升序排列开始,然后不断产生以下一个更大的Permutation直到倒序排列 这样可以用iterative的方法不重复的生成每一个permutation
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-5 10:56:38 | 显示全部楼层
glaciersilent 发表于 2015-7-5 05:26
我认为这题的testcase或者benchmark后来有修改 我早先也是Backtrack做是可以AC的,前两天做就不行了,包括 ...

请问你用的什么语言?LC近来确实有不少改动,不过我刚刚用C++和Java测试了一下,分别是32ms和388ms(用的都是Backtracking),这离后台设定的TLE阈值还有距离。AC应该是不成问题的。

能否让我看看你的TLE代码?
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-5 11:40:11 | 显示全部楼层
glaciersilent 发表于 2015-7-5 05:26
我认为这题的testcase或者benchmark后来有修改 我早先也是Backtrack做是可以AC的,前两天做就不行了,包括 ...

同意,感觉用next permutation既容易写,也符合直观思维。有些情形下递归反倒没有循环好写。
回复 支持 反对

使用道具 举报

 楼主| zh355245849 发表于 2015-7-5 13:15:56 | 显示全部楼层
stellari 发表于 2015-7-5 10:56
请问你用的什么语言?LC近来确实有不少改动,不过我刚刚用C++和Java测试了一下,分别是32ms和388ms(用的 ...

用的java语言。。我贴的这个就是TLE的。。。
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-5 14:02:17 | 显示全部楼层
zh355245849 发表于 2015-7-5 13:15
用的java语言。。我贴的这个就是TLE的。。。

噢,不好意思,我是说想看看@glaciersilent 的代码。楼主的代码没有剪枝,TLE并非意料之外。
回复 支持 反对

使用道具 举报

glaciersilent 发表于 2015-7-5 14:12:23 | 显示全部楼层
stellari 发表于 2015-7-5 10:56
请问你用的什么语言?LC近来确实有不少改动,不过我刚刚用C++和Java测试了一下,分别是32ms和388ms(用的 ...

Never mind.. 我刚又看了下之前写的,考虑疏忽了,因为没有排序,代码如下,另外我run了下我说的那种iterative的方法,两种方法都可以最快到320ms左右,如你所说 backtracking效率并不低
  1. public class Solution {
  2.     List<List<Integer>> result=new ArrayList<>();
  3.     public List<List<Integer>> permuteUnique(int[] nums) {
  4.         if(nums.length==0)
  5.             return result;
  6.         Arrays.sort(nums);//Forget to sort here,which leads to TLE
  7.         List<Integer> left=new LinkedList<Integer>();
  8.         for(int num:nums)
  9.             left.add(num);
  10.         permuteSolver(new ArrayList<Integer>(),left);
  11.         return result;
  12.     }
  13.     private void permuteSolver(List<Integer> per,List<Integer> left){
  14.         if(left.size()==0){
  15.             result.add(new ArrayList<Integer>(per));
  16.             return;
  17.         }
  18.         for(int i=0;i<left.size();i++){
  19.             if(i>0&&left.get(i)==left.get(i-1))
  20.                 continue;
  21.             per.add(left.get(i));
  22.             left.remove(i);
  23.             permuteSolver(per,left);
  24.             left.add(i,per.get(per.size()-1));
  25.             per.remove(per.size()-1);
  26.         }
  27.     }
  28. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 22:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表