有重复项数字的全排列

[编程题]有重复项数字的全排列

热度指数：107672 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。

数据范围： $0 < n \le 8$ ，数组中的值满足 $-1 \le val \le 5$

要求：空间复杂度 $O(n!)$ ，时间复杂度 $O(n!)$

示例1

输入

[1,1,2]

输出

[[1,1,2],[1,2,1],[2,1,1]]

示例2

输入

[0,1]

输出

[[0,1],[1,0]]

算法知识视频讲解

LaN666

发表于 2020-11-22 16:12:37

精华题解题目思路：这道题目跟没有重复项数字的所有排列的做法其实是类似的，只不过区别在于有了重复的数字，如果不加以处理，还是按照原来的方法去做的话，那么就可能会出现重复的结果。例如：[1,1,2]要是利用原先的做***算出两个[1,1,2]，虽然是第一个1和第二个1，但是结果都是112。所以要避免上展开全文

牛客题解官

发表于 2022-04-22 12:29:26

精华题解题目主要信息: 给定一组可能有重复数字的数组，输出该数组的全部排列输出结果按照字典序升序排列举一反三：学习完本题的思路你可以解决如下题目： BM55. 没有重复项数字的全排列 BM58. 字符串的排列 BM60. 括号生成递归+回溯（推荐使用）知识点：递归与回溯递归是一个过程或函数在展开全文

蒙牛麦片

发表于 2021-07-16 22:22:27

精华题解 NC42 有重复项数字的所有排列题意分析：生成所给数字的所有排列。这一题与JZ27字符串的排列基本一样将字符换成了数字题解一（暴力回溯）：回想一下高中所学的排列组合知识：有3个红球，2个白球，1个黑球，请问有多少中排列方式。我们的计算方式是：一个有6个位置，先选择3个位置放红球，再从剩下展开全文

华科不平凡

发表于 2020-09-01 11:22:55

三种方法：回溯——基于辅助数组回溯——基于交换基于库函数next_permutation 方法一：基于辅助数组 // // Created by jt on 2020/9/1. // #include <vector> #include <algorithm> us 展开全文

牛客791761168号

发表于 2022-03-31 20:25:20

使用自带的全排列函数，去重后使用sorted进行字典序排序 from itertools import permutations class Solution: def permuteUnique(self , num: List[int]) -> List[List[int]]: 展开全文

其治帅

发表于 2021-09-17 08:56:35

例: [1, 1, 2, 3]步骤:[1] + permuteUnique([1, 2, 3])中的每一个item[1]重复了，直接跳过[2] + permuteUnique([1, 1, 3])中的每一个item[3] + permuteUnique([1, 1, 2])中的每一个item 基本思展开全文

摸鱼学大师

发表于 2022-02-16 20:14:59

题目主要信息: 给定一组可能有重复数字的数组，输出该数组的全部排列输出结果按照字典序升序排列具体思路: 这道题类似没有重复项数字的全排列，但是因为交换位置可能会出现重复交换的情况，出现的结果需要去重，因此不便于使用交换位置的方法，我们就使用临时变量去组装一个排列的情况：每当我们选取一个数组元展开全文

牛客281174060号

发表于 2022-04-03 11:55:12

这个链接中是解决没有重复项数字的全排列的思路。此时我的总体递归思想是，取出第一个数字，递归得到剩下list的全排列，然后把第一个数字插入到结果的每一个位置。这样一种递归思想确实能得到全排列，但是当有重复数字时，很难将结果按照字典顺序返回。因为这种递归思想中对于重复数字的解决办法是得到递归结果，然后把展开全文