[Leetcode] Permutations 全排列

scq000 发布于2019-08-14 12:31 / 1746人阅读

摘要：每一轮搜索选择一个数加入列表中，同时我们还要维护一个全局的布尔数组，来标记哪些元素已经被加入列表了，这样在下一轮搜索中要跳过这些元素。

Permutations I

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

交换法 复杂度

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

思路

置换实际上是给出所有的排列方式，同样是用深度优先搜索，不过为了避免重复选择的情况，我们要保证两点：第一，所有数必须是数组中的，第二，数组中每个数只能用不多于也不少于一次。如果我们要多带带写一个函数，来判断下一轮搜索该选择哪一个数就很麻烦了。这里有一个技巧，我们可以只将数两两交换，不过交换时只能跟自己后面的交换。

代码

public class Solution {
    
    List> res;
    
    public List> permute(int[] nums) {
        res = new LinkedList>();
        helper(nums, 0);
        return res;
    }
    
    public void helper(int[] nums, int i){
        // 找到转置完成后的解，将其存入列表中
        if(i == nums.length - 1){
            List list = new LinkedList();
            for(int j = 0; j < nums.length; j++){
                list.add(nums[j]);
            }
            res.add(list);
        }
        // 将当前位置的数跟后面的数交换，并搜索解
        for(int j = i; j < nums.length; j++){
            swap(nums, i , j);
            helper(nums, i + 1);
            swap(nums, i, j);
        }
    }
    
    private void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

深度优先搜索 复杂度

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

思路

我们还可以简单的使用深度优先搜索来解决这题。每一轮搜索选择一个数加入列表中，同时我们还要维护一个全局的布尔数组，来标记哪些元素已经被加入列表了，这样在下一轮搜索中要跳过这些元素。

代码

public class Solution {
    
    List> res;
    boolean[] used;
    
    public List> permute(int[] nums) {
        res = new LinkedList>();
        used = new boolean[nums.length];
        List tmp = new LinkedList();
        helper(nums, tmp);
        return res;
    }
    
    private void helper(int[] nums, List tmp){
        if(tmp.size() == nums.length){
            List list = new LinkedList(tmp);
            res.add(list);
        } else {
            for(int idx = 0; idx < nums.length; idx++){
                // 遇到已经加过的元素就跳过
                if(used[idx]){
                    continue;
                }
                // 加入该元素后继续搜索
                used[idx] = true;
                tmp.add(nums[idx]);
                helper(nums, tmp);
                tmp.remove(tmp.size()-1);
                used[idx] = false;
            }
        }
    }
}

Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example, [1,1,2] have the following unique permutations: [1,1,2], [1,2,1], and [2,1,1].

深度优先搜索 复杂度

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

思路

这题和上题的深度优先搜索很相似，区别在于：1、要先将数组排序，确保重复的元素是在一起的。2、除了不能加入之前出现过的元素之外，还不能加入本轮搜索中出现过的元素。如何判断哪些元素本轮出现过呢？我们加过一个数字并搜索后，在这一轮中把剩余的重复数字都跳过就行了，保证每一轮只有一个unique的数字出现。这和Combination Sum II中跳过重复元素的方法是一样的，注意要判断nums[i] == nums[i + 1]，因为for循环结束时i还会额外加1，我们要把i留在最后一个重复元素处。

代码

public class Solution {
    
    List> res;
    boolean[] used;
    
    public List> permuteUnique(int[] nums) {
        res = new LinkedList>();
        used = new boolean[nums.length];
        Arrays.sort(nums);
        List tmp = new LinkedList();
        helper(nums, tmp);
        return res;
    }
    
    private void helper(int[] nums, List tmp){
        if(tmp.size() == nums.length){
            List list = new LinkedList(tmp);
            res.add(list);
        } else {
            for(int idx = 0; idx < nums.length; idx++){
                // 遇到已经加过的元素就跳过
                if(used[idx]){
                    continue;
                }
                
                // 加入该元素后继续搜索
                used[idx] = true;
                tmp.add(nums[idx]);
                helper(nums, tmp);
                tmp.remove(tmp.size()-1);
                used[idx] = false;
                // 跳过本轮的重复元素，确保每一轮只会加unique的数字
                while(idx < nums.length - 1 && nums[idx] == nums[idx + 1]){
                idx++;
            }
            }
        }
    }
}

GPU云服务器云服务器字符串全排列 java 全排列数列字符串全排列算法最快的全排列算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64532.html

leetcode 47 Permutations II

摘要：题目详情题目要求输入一个可能会有重复数字的数组，要求我们输出可能组成的全排列无重复排列。可以用来实现，但这种实现方式复杂度高。另外一种实现思路是，新声明一个数组来存储中元素的使用状况。以这个数组为例。题目详情 Given a collection of numbers that might contain duplicates, return all possible unique ...

Cobub 2019-08-16 11:13 评论0 收藏0
[Leetcode] Permutation Sequence 全排列序列

摘要：找规律复杂度时间空间思路由于我们只要得到第个全排列，而不是所有全排列，我们不一定要将所有可能都搜索一遍。根据全排列顺序的性质，我们可以总结出一个规律假设全排列有个数组成，则第个全排列的第一位是。然后将得到，这个就是下一轮的。 Permutation Sequence The set [1,2,3,…,n] contains a total of n! unique permutati...

testHs 2019-08-14 12:34 评论0 收藏0
leetcode 46 Permutations

摘要：例如有如下的全排列想法这道题是用回溯法的思想解决的。回溯法在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发深度优先搜索，搜索到某个点的时候，先判断该节点是否包含问题的解，如果包含就继续探索，否则就逐层向根节点回溯。题目详情 Given a collection of distinct numbers, return all possible permutations....

jubincn 2019-08-16 11:09 评论0 收藏0
leetcode47 Permutations II

摘要：当前的值如果已经被使用过，则继续判断下一个数值。则当第一个被添加进结果集时，可以继续使用第二个作为元素添加进结果集从而生成。假设将表示为那么结果集中会确保永远在数值的前面，从而避免了和的重复情况出现。题目要求 Given a collection of numbers that might contain duplicates, return all possible unique ...

taoszu 2019-08-14 18:33 评论0 收藏0
leetcode46 Permutation 排列组合

摘要：题目要求也就是得出所有可能的排列组合结果解题思路和代码这题显然采用递归的思路。在这里，我采用实现队列，从队列头获得上一组的结果，和当前元素结合之后，将结果插入到队尾。题目要求 Given a collection of distinct numbers, return all possible permutations. For example, [1,2,3] have the ...

wendux 2019-08-16 10:34 评论0 收藏0