Permutations(Medium)排列

LeetCode Source

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

解题思路1：回溯+DFS

解题思路: 看到这道题，首先第一想法应该是用递归来求解.如果要是用循环来求解，这个时间复杂度应该是比较恐怖了.并且，这个递归是一层一层往深处去走的，打个比方，我们一个循环，首先求得以1开始的看个数的combination，之后再求以2开始的，以此类推，所以开始是对n个数做DFS, n-1个数做DFS...所以应该是对n(n-1)...*1做DFS. 在程序中，我们可以加一些剪枝条件来减少程序时间.

时间复杂度: 在题目分析中，我们提到了对于对n,n-1,...,1做DFS，所以时间复杂度是O(n!)

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if (nums == null || nums.length == 0) return result;

    List<Integer> list = new ArrayList<Integer>();
    dfs(nums, list, result);

    return result;
}

private void dfs(int[] nums, List<Integer> current, List<List<Integer>> result) {
    if (current.size() == nums.length) {
        result.add(new ArrayList<Integer>(current));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        if (current.contains(nums[i]))
            continue;

        current.add(nums[i]);
        dfs(nums, current, result);
        current.remove(current.size() - 1);
    }
}

解题思路2: 迭代,使用Next Permutaion的思想

复杂度

时间 O(N^2) 空间 O(N) 递归栈

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if (nums == null || nums.length == 0) return result;

    Arrays.sort(nums);
    while (true) {
        // step0: add nums into result
        List<Integer> list = new ArrayList<Integer>();
        for (int i : nums) {
            list.add(i);
        }
        result.add(list);

        // step2: find the first nums[k] < nums[k + 1] from the end to start
        int k = -1;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                k = i;
                break;
            }
        }
        if (k == -1) break;

        // step3: find the first nums[l] > nums[k] from the end to start
        int l = nums.length - 1;
        while (nums[l] <= nums[k]) {
            l--;
        }

        // step3: swap between l and k
        int temp = nums[l];
        nums[l] = nums[k];
        nums[k] = temp;

        // step4: reverse between k + 1, nums.length - 1
        reverse(nums, k + 1, nums.length - 1);
    }

    return result;
}

private void reverse(int[] nums, int lb, int ub) {
    while (lb < ub) {
        int temp = nums[lb];
        nums[lb] = nums[ub];
        nums[ub] = temp;
        lb++;
        ub--;
    }
}

References

1 Permutations from kancloud

2 Next Permutation

3 Permutation Sequence