LeetCode–046–全排列(java)

 1 class Solution {
 2     public static void swap(int[] nums_,int a,int b){
 3             int temp = nums_[a];
 4             nums_[a] = nums_[b];
 5             nums_[b] = temp;
 6         }
 7     public static boolean isEqual(int[] a,int[] b){
 8         for(int i = 0;i < a.length;i++){
 9             if(a[i] != b[i])return false;
10         }
11         return true;
12     }
13     public List<List<Integer>> permute(int[] nums) {
14         List<List<Integer>> res = new ArrayList();
15             List<Integer> lists = new ArrayList();
16             if(nums.length < 2){
17                 lists.add(nums[0]);
18                 res.add(lists);
19                 return res;
20             }
21             int[] nums_ = new int[nums.length];
22             for(int k = 0;k < nums.length;k++){
23                 nums_[k] = nums[k];
24                 lists.add(nums[k]);
25                 
26             }
27             res.add(new ArrayList(lists));
28             lists.removeAll(lists);
29             swap(nums_,0,1);
30             for(int j = 0;j < nums.length;j++){
31                 lists.add(nums_[j]);
32             }
33             res.add(new ArrayList(lists));
34             int i = 1;
35             while(!isEqual(nums,nums_)){
36                 if(i+1<nums.length){
37                     swap(nums_,i,i+1);
38                     if(!isEqual(nums,nums_)){
39                         lists.removeAll(lists);
40                         for(int j = 0;j < nums.length;j++){
41                             lists.add(nums_[j]);
42                         }
43                         res.add(new ArrayList(lists));
44                     }
45                     i++;
46                 }else{
47                     i = 0;
48                 }
49             }
50             return res;
51     }
52     
53 }

 1 class Solution {
 2    
 3     public List<List<Integer>> permute(int[] nums) {
 4         List<List<Integer>> res = new ArrayList<>();
 5         if(nums== null || nums.length ==0)return res;
 6         helper(res,new ArrayList<>(),nums);
 7         return res;
 8     }
 9     public void helper(List<List<Integer>> res,List<Integer> list,int[] nums){
10         if(list.size() == nums.length){
11             res.add(new ArrayList<>(list));
12             return;
13         }
14         for(int i = 0;i < nums.length;i++){
15             if(list.contains(nums[i]))continue;//contaisn的时间复杂度为O(N)
16             list.add(nums[i]);
17             helper(res,list,nums);
18             list.remove(list.size()-1);
19         }
20     } 
21     
22 }

 1 class Solution {
 2    
 3     public List<List<Integer>> permute(int[] nums) {
 4         List<List<Integer>> res = new ArrayList<>();
 5         if(nums.length == 0 || nums == null)return res;
 6         helper(res,0,nums);
 7         return res;
 8     } 
 9     public void helper(List<List<Integer>> res,int start,int[] nums){
10         if(start == nums.length){
11             List<Integer> list = new ArrayList<>();
12             for(int q:nums){
13                 list.add(q);
14             }
15             res.add(new ArrayList<>(list));
16             return;
17         }
18         for(int i = start;i < nums.length;i++){
19             swap(nums,start,i);
20             helper(res,start+1,nums);
21             swap(nums,start,i);
22         }
23         
24     }
25     public void swap(int[] nums,int l,int m){
26         int temp = nums[l];
27         nums[l] = nums[m];
28         nums[m] = temp;
29     }
30     
31 }