46. Permutations-白红宇

46. Permutations

阅读量：6479 次

发布时间：2019-06-23

本文共 8418 字，大约阅读时间需要 28 分钟。

题目：

Given a collection of numbers, return all possible permutations.

For example,

[1,2,3] have the following permutations:

[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Hide Tags

链接：

题解：

求数组的全排列。需要用到DFS和Backtracking。原理是从0到数组长度N，每次对之前加入的元素进行回溯。注意此解法假定输入数组之中没有重复元素。

Time Complexity - O(n!)， Space Complexity - O(n)。

public class Solution {    public ArrayList
     
      
       > permute(int[] nums) {        ArrayList
       
        
         > result = new ArrayList
         
          
           >(); if(nums == null || nums.length == 0) return result; Arrays.sort(nums); ArrayList
           
             list = new ArrayList
            
             (); helper(result, list, nums); return result; } private void helper(ArrayList
             
              
               > result, ArrayList
               
                 list, int[] nums){ if(list.size() == nums.length){ //in this problem we assume no duplicate exists in input array result.add(new ArrayList
                
                 (list)); return; } for(int i = 0; i < nums.length; i++){ if(list.contains(nums[i])) continue; list.add(nums[i]); helper(result, list, nums); list.remove(list.size() - 1); } }}

二刷:

Java:

一般来说可以分为两种做法，一种是DFS + backtracking, 另外一种是利用next permutation一样的做法来一个一个求出next permutation。

Next permutation做法：

为了使用Arrays.asList(new Nums)，我们先把int[] nums转换为Integer[] newNums。然后新建一个method - boolean hasNextPermutation。把newNums排序以后，转换为ArrayList，加入到结果集中。接下来我们进入循环，当hasNext为true时，我们在hasNext的函数体里面已经完成了交换，把这时候的nums转换为ArrayList加入到结果集中，然后进行下一次判断。最后返回结果。速度比较慢。

Time Complexity - O(n!), Space Complexity - O(n)

public class Solution {    public List
     
      
       > permute(int[] nums) {        List
       
        
         > res = new ArrayList<>();        if (nums == null || nums.length == 0) {            return res;        }        Integer[] newNums = new Integer[nums.length];        for (int i = 0; i < nums.length; i++) {            newNums[i] = nums[i];        }        Arrays.sort(newNums);        res.add(new ArrayList
         
          (Arrays.asList(newNums)));        while (hasNextPermutation(newNums)) {            res.add(new ArrayList
          
           (Arrays.asList(newNums))); } return res; } private boolean hasNextPermutation(Integer[] newNums) { for (int i = newNums.length - 2; i >= 0; i--) { if (newNums[i] < newNums[i + 1]) { for (int j = newNums.length - 1; j > i; j--) { if (newNums[j] > newNums[i]) { swap(newNums, i, j); reverse(newNums, i + 1, newNums.length - 1); return true; } } } } return false; } private void swap(Integer[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } private void reverse(Integer[] nums, int i, int j) { while (i < j) { swap(nums, i++, j--); } }}

DFS + backtracking(使用list.contains去重复):

我们也可以用DFS+Backtracking来做。这里需要建立一个helper函数permute和一个辅助List<Integer> onePerm。当onePerm.size() == nums.size()的时候，我们把这个辅助list加入到结果中。否则我们进行从0到nums.length - 1的遍历，在这个遍历过程中我们使用了DFS+回溯。我们假设给定nums中不含重复元素，一个重要的去重步骤是，假如当前辅助List里已经有nums[i]了，那么我们进行跳过。这一步使用了O(n)的复杂度，所以导致整个过程比较慢。

Time Complexity - O(n!)， Space Complexity O(n)。 (其实由于有这一步list.contains()递归复杂度应该是 (n * 1) *((n - 1) * 2) *((n - 2) * 3)...)应该等于 ∏(1²*..。 *n²)

public class Solution {    public List
     
      
       > permute(int[] nums) {        List
       
        
         > res = new ArrayList<>();        if (nums == null || nums.length == 0) {            return res;        }        Arrays.sort(nums);        List
         
           onePerm = new ArrayList
          
           (); permute(res, onePerm, nums); return res; } public void permute(List
           
            
             > res, List
             
               onePerm, int[] nums) { if (onePerm.size() == nums.length) { res.add(new ArrayList
              
               (onePerm)); return; } for (int i = 0; i < nums.length; i++) { if (onePerm.contains(nums[i])) { continue; } onePerm.add(nums[i]); permute(res, onePerm, nums); onePerm.remove(onePerm.size() - 1); } }}

DFS:

也可以用类似自底向上新建立List<Integer>的方式来跳过用List.contains来去重复的过程。

我们先传入辅助函数一个空ArrayList<>()

遍历数组，当index i <= newPerm.size()时，我们把num[pos]这个元素分别加入到这个newPerm的从0 到 newPerm.size()的不同位置中去

然后再进行下一层dfs，继续加入nums中的下一个元素

这样做的坏处是空间复杂度会比较高，每一层的每次遍历都会新开一个ArrayList，假如nums很大的话，理论上有可能会触发更多次的garbage collection。但试验了几次以后比上面的两个solution要快，先存着当做一种不同的思路了。

还有一点是这里的code没有对nums排序，好像这种方法排序与不排序并没有什么关系....

Time Complexity - O(n!)， Space Complexity - O(n!)

public class Solution {    public List
     
      
       > permute(int[] nums) {        List
       
        
         > res = new ArrayList<>();        if (nums == null || nums.length == 0) {            return res;        }        getPermutions(res, new ArrayList
         
          (), nums, 0);        return res;    }        public void getPermutions(List
          
           
            > res, List
            
              onePerm, int[] nums, int pos) { if (onePerm.size() == nums.length) { res.add(new ArrayList
             
              (onePerm)); return; } for (int i = 0; i <= onePerm.size(); i++) { List
              
                newPerm = new ArrayList<>(onePerm); newPerm.add(i, nums[pos]); getPermutions(res, newPerm, nums, pos + 1); } }}

三刷:

还是使用了next permutation的方法。需要再练习练习。还有一些方法，比如不断地把第i位的元素插入到 i - 1的结果中去。或者不断递归swap start和i并且回溯，都可以完成。Discuss区的大神们写得更好。

查了一下资料，更好的方法应该是Johnson-Trotter法，根据上一个permutation的奇偶性来升序或者降序地添加新元素，也是O(n!)的时间复杂度。但这么做可能导致结果是无序的。

Java:

使用Next Permutation:

public class Solution {    public List
     
      
       > permute(int[] nums) {        List
       
        
         > res = new ArrayList<>();        if (nums == null || nums.length == 0) return res;        Arrays.sort(nums);        do {            List
         
           permu = new ArrayList<>();            for (int num : nums) permu.add(num);            res.add(permu);        } while (hasNextPermutation(nums));        return res;    }        private boolean hasNextPermutation(int[] nums) {        int len = nums.length;        for (int i = len - 2; i >= 0; i--) {            if (nums[i] < nums[i + 1]) {                for (int j = len - 1; j > i; j--) {                    if (nums[j] > nums[i]) {                        swap(nums, i, j);                        reverse(nums, i + 1, len - 1);                        return true;                    }                       }            }        }        return false;    }        private void swap(int[] nums, int i, int j) {        int tmp = nums[i];        nums[i] = nums[j];        nums[j] = tmp;    }        private void reverse(int[] nums, int i, int j) {        while (i < j) swap(nums, i++, j--);    }}

通过不断swap: 速度非常快

public class Solution {    public List
     
      
       > permute(int[] nums) {        List
       
        
         > res = new ArrayList<>();        permute(res, nums, 0);        return res;    }        private void permute(List
         
          
           > res, int[] nums, int pos) { if (pos == nums.length) { List
           
             list = new ArrayList<>(); for (int i = 0; i < nums.length; i++) list.add(nums[i]); res.add(list); return; } for (int i = pos; i < nums.length; i++) { swap(nums, pos, i); permute(res, 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; }}

通过不断insert下一个元素

public class Solution {    public List
     
      
       > permute(int[] nums) {        List
       
        
         > res = new ArrayList<>();        if (nums.length == 0) return res;        res.add(new ArrayList<>());        for (int i = 0; i < nums.length; i++) {            List
         
          
           > newRes = new ArrayList<>(); for (int j = 0; j <= i; j++) { for (List
           
             l : res) { List
            
              list = new ArrayList<>(l); list.add(j, nums[i]); newRes.add(list); } } res = newRes; } return res; }}