【LeetCode】Permutations II 解题报告

时间:2021-11-07 09:01:18

【题目】

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

【解析】

题意:求一个数组的全排列。与【LeetCode】Permutations 解题报告 不同的是,数组中的数有反复。

对于全排列,如今比較经常使用的算法就是依据 【LeetCode】Next Permutation 解题报告 从小到大逐个找出全部的排列。

算法:回溯、字典序法。

public class Solution {
List<List<Integer>> ans = new ArrayList<List<Integer>>(); public List<List<Integer>> permuteUnique(int[] num) {
Arrays.sort(num); //首先得把原始数组加入到结果集
List<Integer> list = new ArrayList<Integer>();
for (int x : num) {
list.add(x);
}
ans.add(list); //逐个加入下一个解
for (int i = 1; i < factorial(num.length); i++) {
nextPermutation(num);
} return ans;
} public void nextPermutation(int[] num) {
//找到最后一个正序
int i = num.length - 1;
while (i > 0 && num[i] <= num[i - 1]) {
i--;
}
if (i <= 0) return; //找到最后一个比num[i-1]大的数
int j = num.length - 1;
while (j >= i && num[j] <= num[i - 1]) {
j--;
} //交换
int tmp = num[i - 1];
num[i - 1] = num[j];
num[j] = tmp; //逆排i-1之后的数
int l = i, r = num.length - 1;
while (l < r) {
tmp = num[l];
num[l] = num[r];
num[r] = tmp;
l++;
r--;
} //加入到结果集
List<Integer> list = new ArrayList<Integer>();
for (int x : num) {
list.add(x);
}
ans.add(list);
} public int factorial(int n) {
return n == 0 ? 1 : n * factorial(n - 1);
}
}

相关题目:【LeetCode】Permutations 解题报告 和 【LeetCode】Next Permutation
解题报告

【LeetCode】Permutations II 解题报告的更多相关文章

  1. LeetCode&colon; Permutations II 解题报告

    Permutations II Given a collection of numbers that might contain duplicates, return all possible uni ...

  2. 【LeetCode】47&period; Permutations II 解题报告(Python & C&plus;&plus;)

    作者: 负雪明烛 id: fuxuemingzhu 个人博客: http://fuxuemingzhu.cn/ 目录 题目描述 题目大意 解题方法 方法一:递归 方法二:回溯法 日期 题目地址:htt ...

  3. LeetCode&colon; N-Queens II 解题报告

    N-Queens II (LEVEL 4 难度级别,*5) Follow up for N-Queens problem.

  4. LeetCode&colon; Combination Sum 解题报告

    Combination Sum Combination Sum Total Accepted: 25850 Total Submissions: 96391 My Submissions Questi ...

  5. LeetCode&colon; Unique Paths II 解题报告

    Unique Paths II Total Accepted: 31019 Total Submissions: 110866My Submissions Question Solution  Fol ...

  6. 【LeetCode】Pascal's Triangle II 解题报告

    [LeetCode]Pascal's Triangle II 解题报告 标签(空格分隔): LeetCode 题目地址:https://leetcode.com/problems/pascals-tr ...

  7. 【LeetCode】375&period; Guess Number Higher or Lower II 解题报告(Python)

    [LeetCode]375. Guess Number Higher or Lower II 解题报告(Python) 作者: 负雪明烛 id: fuxuemingzhu 个人博客: http://f ...

  8. 【LeetCode】731&period; My Calendar II 解题报告(Python)

    [LeetCode]731. My Calendar II 解题报告(Python) 作者: 负雪明烛 id: fuxuemingzhu 个人博客: http://fuxuemingzhu.cn/ 题 ...

  9. 【LeetCode】522&period; Longest Uncommon Subsequence II 解题报告(Python)

    [LeetCode]522. Longest Uncommon Subsequence II 解题报告(Python) 标签(空格分隔): LeetCode 作者: 负雪明烛 id: fuxuemin ...

随机推荐

  1. Oracle备库TNS连接失败的分析

    今天在测试12c的temp_undo的时候,准备在备库上测试一下,突然发现备库使用TNS连接竟然失败. 抛出的错误如下: $ sqlplus sys/oracle@testdb as sysdba S ...

  2. bzoj 2287&colon; 【POJ Challenge】消失之物

    Description ftiasch 有 N 个物品, 体积分别是 W1, W2, ..., WN. 由于她的疏忽, 第 i 个物品丢失了. "要使用剩下的 N - 1 物品装满容积为 x ...

  3. java 入门 第二季2

    (1). 封装 封装类的时候属性用private,方法getter和setter用public 将类的某些信息隐藏在类内部,不允许外部程序直接访问,而是通过该类提供的方法来实现对隐藏信息的操作和访问 ...

  4. easyUI之Combo

    Combo组件为自定义下拉列表组件,无class的加载方式,主要是通过jquery的方式.它依赖于validatebox,可以用它的很多属性.例如: 前台: <div id="box& ...

  5. ubunut 查看port被哪个程序占用

    查看8087port被哪个程序占用 lsof -i :8087 -n

  6. D&period; Longest Subsequence

    D. Longest Subsequence time limit per test 2 seconds memory limit per test 256 megabytes input stand ...

  7. &lbrack;TensorFlow 团队&rsqb; TensorFlow 数据集和估算器介绍

    发布人:TensorFlow 团队 原文链接:http://developers.googleblog.cn/2017/09/tensorflow.html TensorFlow 1.3 引入了两个重 ...

  8. vue--js里跳转页面

    我们知道在vue里进行页面跳转的话,我们使用<router-link>这个标签 那在构造函数里我们不能直接操纵DOM元素,我们又该如何进行页面跳转呢? 步骤1: 我们先在DOM里设置三个按 ...

  9. FineUI经典项目展示(2)基础管理系统(附在线演示)

    本系列<FineUI经典项目展示>文章将会集中展示一批使用FineUI(开源版).专业版.MVC版的经典项目. 如果你希望自己的FineUI项目出现在这个舞台,请到官网论坛提交申请: ht ...

  10. CentOS使用Ubuntu的start-stop-daemon来启动守护进程

    在CentOS下使用守护进程启动有/etc/init.d/functions文件下的daemon方法,但如果要使用Ubuntu下的start-stop-daemon方法也可以实现. 安装如下: # 下 ...