首页 > 其他 > 详细

47. 全排列 II

时间:2021-06-12 00:49:38      阅读:24      评论:0      收藏:0      [点我收藏+]

给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。

 示例 1:

输入:nums = [1,1,2]
输出:
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2:

输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        if (nums.length == 0)
            return res;
        List<Integer> temp = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            temp.add(nums[i]);
        }
        pereur(nums, temp, 0, nums.length);
        return res;

    }

    private void pereur(int[] nums, List<Integer> lst, int level, int length) {
        if (level == length) {
            for (int i = 0; i < res.size(); i++) {
                if (res.get(i).equals(lst))
                    return;
            }
            res.add(new ArrayList<Integer>(lst));
            System.out.println(lst);
            return;
        }

        for (int i = level; i < nums.length; i++) {
            Collections.swap(lst, level, i);
            pereur(nums, lst, level + 1, length);
            Collections.swap(lst, level, i);
        }

    }

时间复杂度:O(n\times n!)O(n×n!),其中 nn 为序列的长度

空间复杂度:O(N)

47. 全排列 II

原文:https://www.cnblogs.com/xiaoming521/p/14876642.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!