permutationII疑问

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. }

复制代码