资讯专栏INFORMATION COLUMN

【力扣】47. 全排列 II

blastz / 3086人阅读

摘要:题目给定一个可包含重复数字的序列,按任意顺序返回所有不重复的全排列。示例输入输出示例输入输出提示答案回溯法使用数组判断是否访问过,排序后跳过与前一个相同的

题目:
给定一个可包含重复数字的序列 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]]

提示:

1 <= nums.length <= 8
-10 <= nums[i] <= 10

答案:

class Solution {    List<List<Integer>> lists;    public List<List<Integer>> permuteUnique(int[] nums) {        //回溯法,使用数组判断是否访问过,排序后跳过与前一个相同的        boolean[] visited = new boolean[9];        lists = new ArrayList<>();        List<Integer> list = new ArrayList<>();        Arrays.sort(nums);        backTrace(list, nums, visited);        return lists;    }    public void backTrace(List<Integer> list, int[] nums, boolean[] visited){        if(list.size() == nums.length) lists.add(new ArrayList<>(list));        for(int i = 0; i < nums.length; i++){            if(i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) continue;            if(visited[i]) continue;            visited[i] = true;            list.add(nums[i]);            backTrace(list, nums, visited);            list.remove(list.size() - 1);            visited[i] = false;        }    }}

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

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

相关文章

  • 力扣(LeetCode)47

    摘要:示例输入输出解答这一题可以利用求下一个排列算法来求解,对原数组排序,然后加入一个结果,接着不断求下一个排列,直到没有下一个排列为止。而下一个排列的求解可以参考下一个排列代码 题目地址:https://leetcode-cn.com/probl...题目描述:给定一个可包含重复数字的序列,返回所有不重复的全排列。 示例: 输入: [1,1,2]输出:[ [1,1,2], [1,2,1...

    NusterCache 评论0 收藏0
  • leetcode 47 Permutations II

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

    Cobub 评论0 收藏0
  • 6-9月技术文章汇总

    摘要:分布式的管理和当我在谈论架构时我在谈啥状态码详解无状态协议和请求支持哪些方法分层协议栈有哪些数据结构运用场景说说你常用的命令为什么要有包装类面向对象的特征是啥是啥有什么好处系统设计工程在线诊断系统设计与实现索引背后的数据结构及算法原理软技能 HTTP 【HTTP】分布式session的管理 【HTTP】Cookie和Session 【HTTP】当我在谈论RestFul架构时我在谈啥?...

    miya 评论0 收藏0
  • 力扣(LeetCode)46

    摘要:题目地址题目描述给定一个没有重复数字的序列,返回其所有可能的全排列。 题目地址:https://leetcode-cn.com/probl...题目描述:给定一个没有重复数字的序列,返回其所有可能的全排列。 示例: 输入: [1,2,3]输出:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]解答:利用递归,我们可...

    李增田 评论0 收藏0
  • 力扣(LeetCode)756

    摘要:题目地址题目描述给出集合,其所有元素共有种排列。说明给定的范围是。第二种是回溯法求全排列,设置一个全局变量为当前求出的排列数,求出第个全排列,也就是时,停止所有递归否则会超时。 题目地址:https://leetcode-cn.com/probl...题目描述:给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。 按大小顺序列出所有排列情况,并一一标记,当 n = 3 时,...

    Keven 评论0 收藏0

发表评论

0条评论

blastz

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<