友链
姚屹晨

leetcode - [46] Permutations

2020/04/28

题目描述

Given a collection of distinct integers, return all possible permutations.

统计一个非重复数组的排列情况。

举个例子：

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Update at 2020_0825

避免使用list.contains(x)，因为它的时间复杂度为O(n)。

使用一个boolean数组判断当前元素是否存在于child中，注意用的是下标。

class Solution {

    boolean[] used;
    LinkedList<Integer> child = new LinkedList<>();
    List<List<Integer>> ans = new LinkedList<>();

    private void dfs(int[] nums, int u){
        int n = nums.length;
        if (u == n){
            ans.add(new LinkedList<>(child));
            return;
        }
        for (int i = 0; i < n; i++){
            if (!used[i]){
                used[i] = true;
                child.add(nums[i]);
                dfs(nums, u + 1);
                used[i] = false;
                child.removeLast();
            }
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        int n = nums.length;
        if (n == 0) return ans;
        used = new boolean[n];
        dfs(nums, 0);
        return ans;
    }
}

Update at 2020_0705

听了Y总的课，才知道这原来是一道经典的DFS题。

之前画的流程图太过于复杂，来看一种简单、更容易理解的示意图：

再来看下代码实现：

代码其实和原来差不多，只不过思考的方式发生了转换。

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        
        List<List<Integer>> ans = new LinkedList<>();
        if (nums.length == 0) return ans;
        dfs(nums, ans, new LinkedList<>());
        return ans;
    }
    
    private void dfs(int[] nums, List<List<Integer>> ans, LinkedList<Integer> child){
        
        if (child.size() == nums.length){
            ans.add(new LinkedList<>(child));
        }
        
        for (int n: nums){
            if (child.contains(n)) continue;
            child.add(n);
            dfs(nums, ans, child);
            // 恢复现场
            child.removeLast();
        }
    }
}

Update at 2020_0618

类似题目：

[78] Subsets [90] Subsets II

那么这道题目与SubSets的区别是什么呢？

首先，Subsets一旦进入递归方法，则先将子列表加入结果列表中。

但是，Permutations不能这样做，需要判断条件。

只有当child子列表中元素数量等于原始数组长度时，才添加。

第二，递归方法中的遍历方式不同，在SubSets中需要一个记录当前索引的变量cur。

但是，Permutations不需要，因为它需要回过头来添加之前的元素。

那么它是如何做到排列的呢？

其实就是不断地从头到尾遍历原始数组，如果数组中包含当前值，则跳过。

来看下实现：

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        
        List<List<Integer>> ans = new LinkedList<>();
        bt(nums, ans, new LinkedList<>());
        return ans;
    }
    
    private void bt(int[] nums, List<List<Integer>> ans, LinkedList<Integer> child){
        
        int len = nums.length;
        if (child.size() == len){
            ans.add(new LinkedList<>(child));
        } else {
            for (int i = 0; i < len; i++){
                // Skip duplicates
                if (child.contains(nums[i])){
                    continue;
                }
                child.add(nums[i]);
                bt(nums, ans, child);
                child.removeLast();
            }
        }
    }
}

解法1

Thanks @issac3

这位大侠在讨论区同时发了好几道类题目的题解，我要花几天时间好好消化消化~~

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    doPermute(list, nums, new ArrayList<>());
    return list;
}

public void doPermute(List<List<Integer>> list, int[] nums, List<Integer> tmpList){
    if (nums.length == tmpList.size()){
        // Be careful
        list.add(new ArrayList(tmpList));
    } else {
        for (int i = 0; i < nums.length; i++){
            if (tmpList.contains(nums[i])) continue;
            tmpList.add(nums[i]);
            doPermute(list, nums, tmpList);
            tmpList.remove(tmpList.size() - 1);
        }
    }
}

Amazing!


一位喜欢提问、尝试的程序员

（转载本站文章请注明作者和出处 姚屹晨-yaoyichen）

Post Directory