关上过去和未来的铁门，活在“今天”这个舱室中。 ——《人性的优点》
创新互联公司 - 服务器机柜租用，四川服务器租用，成都服务器租用，四川网通托管,绵阳服务器托管，德阳服务器托管，遂宁服务器托管，绵阳服务器托管，四川云主机，成都云主机，西南云主机，服务器机柜租用，西南服务器托管，四川/成都大带宽，大带宽服务器，四川老牌ＩＤＣ服务商
47. 全排列 II
给定一个可包含重复数字的序列 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
思路：（回溯）
此题是 46. 全排列 的进阶
- 但是这道题有了一点改变，那么就是列表里面有重复数字，全排列的结果，相同答案只算一种，那么我们就要考虑重复。
- 当然因为题目没有说该队列有序，所以要先排序。
判断的时候加上：
if(i >0 && nums[i] == nums[i-1] && hasVisited[i-1] == false) {
continue;
}
其中最为关键的是 hasVisited[i-1] == false ，用来去重，就是限制一下两个相邻的重复的访问顺序
举个栗子 ：
对于两个相同的数 1 1 ，我们将其命名为 a b，a 表示第一个 1 ，b 表示第二个 1
- 如果不去重得的话，会有两种重复排列 a b，b a ，我们只需取其中任意一种排列即可；
- 为了达到目的，限制一下 a ，b 的访问顺序即可；
- 比如 我们只取 a b 这个排列的话，只有当 nums[i - 1] 访问后，我们才去访问 nums[i] ，
- 也就是说 如果 hasVisited[i-1] == false 的话， 则 continue 跳过。
举另个栗子 ：
去重最为关键的代码为：
if(i >0 && nums[i] == nums[i-1] && hasVisited[i-1] == false) {
continue;
}
但如果改成 hasVisited[i-1] == true ,也是正确的， 去重代码如下：
if(i >0 && nums[i] == nums[i-1] && hasVisited[i-1] == true) {
continue;
}
这是为什么呢？
- hasVisited[i-1] == false ，是对树层中前一位去重；
- hasVisited[i-1] == true ，是对树枝前一位去重；
（借用一下别人的图进行理解）：
如果 是三个相同的数 1 1 1
树层上去重（hasVisited[i-1] == false），树形结构如下：
树枝上去重（hasVisited[i-1] == true），树形结构如下：
观察上图可以得出：
- 树层上对前一位去重非常彻底，效率很高；
- 树枝上对前一位去重虽然最后可以得到答案，但是做了很多无用搜索。
代码：（Java）
import java.util.ArrayList;
import java.util.List;
public class all_permute {public static void main(String[] args) {// TODO 自动生成的方法存根
int [] nums = {1, 1, 2};
System.out.println(permuteUnique(nums));
}
public static List>permuteUnique(int[] nums) {List>permutes = new ArrayList<>();
Listpermute = new ArrayList<>();
if(nums == null || nums.length == 0) { return permutes;
}
int flag = 0;//标记
for(int i = 1; i< nums.length ; i++) {//冒泡排序
for(int j = 0; j< nums.length - i; j++) { if(nums[j] >nums[j+1]) {int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
flag++;
}
}
if(flag == 0)
break;
}
boolean [] hasVisited = new boolean[nums.length];
backTracking(nums, hasVisited, permute, permutes);
return permutes;
}
private static void backTracking(int[] nums, boolean[] hasVisited, Listpermute, List>permutes) {// TODO 自动生成的方法存根
if(permute.size() == hasVisited.length) { permutes.add(new ArrayList<>(permute));
return;
}
for(int i = 0; i< nums.length; i++) { if(hasVisited[i]) { continue;
}
if(i >0 && nums[i] == nums[i-1] && hasVisited[i-1] == false) { continue;
}
hasVisited[i] = true;
permute.add(nums[i]);
backTracking(nums, hasVisited, permute, permutes);
permute.remove(permute.size() - 1);
hasVisited[i] = false;
}
}
}
运行结果：
复杂度分析：
时间复杂度：
O
(
n
×
n
!
)
O(n×n!)
O(n×n!)，其中 n 为序列的长度。
算法的复杂度首先受 backTracking 的调用次数制约，backTracking 的调用次数为
∑
k
=
1
n
P
(
n
,
k
)
\sum_{k=1}^{n} P(n, k)
∑k=1nP(n,k)次，其中
P
(
n
,
k
)
=
n
!
(
n
−
k
)
!
=
n
(
n
−
1
)
…
(
n
−
k
+
1
)
P(n, k)=\frac{n !}{(n-k) !}=n(n-1) \ldots(n-k+1)
P(n,k)=(n−k)!n!=n(n−1)…(n−k+1)，该式被称作 n 的 k - 排列，或者部分排列。
而
∑
k
=
1
n
P
(
n
,
k
)
=
n
!
+
n
!
1
!
+
n
!
2
!
+
n
!
3
!
+
…
+
n
!
(
n
−
1
)
!
<
2
n
!
+
n
!
2
+
n
!
2
2
+
n
!
2
n
2
<
3
n
!
\sum_{k=1}^{n} P(n, k)=n !+\frac{n !}{1 !}+\frac{n !}{2 !}+\frac{n !}{3 !}+\ldots+\frac{n !}{(n-1) !}<2 n !+\frac{n !}{2}+\frac{n !}{2^{2}}+\frac{n !}{2^{n} 2}<3 n !
∑k=1nP(n,k)=n!+1!n!+2!n!+3!n!+…+(n−1)!n!<2n!+2n!+22n!+2n2n!<3n!
, 这说明 backTracking 的调用次数是
O
(
n
!
)
O(n!)
O(n!)的。
而对于 backTracking调用的每个叶结点（最坏情况下没有重复数字共
n
!
n!
n!个），我们需要将当前答案使用
O
(
n
)
O(n)
O(n)的时间复制到答案数组中，相乘得时间复杂度为
O
(
n
×
n
!
)
O(n×n!)
O(n×n!)。
因此时间复杂度为
O
(
n
×
n
!
)
O(n×n!)
O(n×n!)。
空间复杂度：
O
(
n
)
O(n)
O(n)。我们需要
O
(
n
)
O(n)
O(n)的标记数组，同时在递归的时候栈深度会达到
O
(
n
)
O(n)
O(n)，因此总空间复杂度为
O
(
n
+
n
)
=
O
(
2
n
)
=
O
(
n
)
O(n+n)=O(2n)=O(n)
O(n+n)=O(2n)=O(n)。
注：仅供学习参考！
题目来源：力扣
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
网站标题：47.全排列II-创新互联
网站地址：
http://www.cdkjz.cn/article/geepg.html
