Leetcode-46: Permutations

[zeqing-guo]

Description

Given a collection of distinct 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].

My Solution

代码的run time是6 ms (13.69%)，时间复杂度是，空间复杂度是。

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        int len = nums.length;
        LinkedList<List<Integer>> ll = new LinkedList<>();
        if (len == 0) {
            return ll;
        }

        ll.add(Arrays.asList(new Integer[]{nums[0]}));
        ll.add(null);
        for (int i = 2; i <= len; ++i) {
            int num = nums[i - 1];
            for (List<Integer> lli = ll.remove(0); lli != null; lli = ll.remove(0)) {
                for (int j = 0; j < i; ++j) {
                    LinkedList<Integer> newLli = new LinkedList<>(lli);
                    newLli.add(j, num);
                    ll.add(newLli);
                }

            }
            ll.add(null);
        }
        ll.removeLast();
        return ll;
    }
}

Analysis

全排列问题。迭代写法模仿了递归的写法，但是是从底而上的。以nums = [1,2,3]举例：

1. 构造一个元素的情况：p = [[1]]。
2. 再从长度为k构造长度为k+1的情况。将p中的元素逐个取出，在元素的空隙中插入nums[k + 1]，然后再放回数组中，注意整个过程要做成一个queue或者从头部取出从尾部放回，也可以从尾部取出从头部放回。
3. 当长度为nums.length时结束构造，输出结果。

总结：

1. 不知道为什么我写的代码跑得比较慢，我看了看和我一样思路的递归代码run time只有2 ms。或许得找个大神问问？
2. List<List<Integer>>可以写成LinkedList<List<Integer>>但不能写成LinkedList<LinkedList<Integer>>，这个应该是协变的问题。
3. 复制一个List list可以写成new List(list)。