题目链接: https://leetcode-cn.com/problems/permutations-ii/
题目大意:
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
看完题目的第一感觉，是一道搜索题，可以dfs递归排列出所有情况。
但是本题有一个附加条件: 输入的数字可重复，但是输出的结果不能重复。
思路一
在dfs输出全排列的情况下，加一个set，用于存储每一次排列拼接成的字符串，比如排列1是[1,1,2]，拼接成的字符串是"1,1,2,"，如果之后的排列拼接成的字符串在set中已存在，就不放入最终的结果集。
代码如下
class Solution {
private int[] nums;
// mark[i] = 0 表示nums[i]未使用，mark[i] = 1表示nums[i]已使用
private int[] mark;
private int length;
// 存放每一次符合条件的排列
private List<Integer> tempList;
// 最终结果集
private List<List<Integer>> resultList;
private StringBuilder stringBuilder;
private Set<String> set;
public List<List<Integer>> permuteUnique(int[] nums) {
length = nums.length;
// 使用递归时，每一次递归都要创建栈，应尽量减少方法参数，因此定义成成员变量
this.nums = nums;
mark = new int[length];
for (int i = 0; i < length; i++) {
mark[i] = 0;
}
tempList = new ArrayList<>(length);
resultList = new ArrayList<>();
stringBuilder = new StringBuilder();
set = new HashSet<>();
dfsPermute(0);
return resultList;
}
/**
* index表示当前排列已经有多少元素
*/
public void dfsPermute(int index) {
if (index == length) {
String str = stringBuilder.toString();
if (!set.contains(str)) {
// 没有重复，放入最终结果集
resultList.add(new ArrayList<>(tempList));
set.add(str);
}
}
for (int i = 0; i < length; i++) {
// 如果nums[i]未被使用，放入本次排列
if (mark[i] == 0) {
// 把nums[i]标记为已使用
mark[i] = 1;
// 将元素放入本次排列
tempList.add(nums[i]);
String tempStr = String.valueOf(nums[i]) + ",";
// 拼接本次元素
stringBuilder.append(tempStr);
// 递归搜索
dfsPermute(index + 1);
// 把nums[i]标记为未使用
mark[i] = 0;
// 移除本次元素
tempList.remove(tempList.size() - 1);
// 移除本次元素，注意delete方法是左闭右开
stringBuilder.delete(stringBuilder.length() - tempStr.length(), stringBuilder.length());
}
}
}
}
第一个思路成功AC，但是耗时104ms太长了，继续优化。
思路二
第一个思路虽然可以AC，但是存在重复的搜索，以[1,1,2]为例，第一次搜索，以第一个1开头，找到了[1,1,2]、[1,2,1]这两种排列，第二次搜索，以第二个1开头，找到的还是[1,1,2]、[1,2,1]这两种排列。
显然，开头的数字，如果是一样的，搜索出的结果也是一样的，因此第二个思路就是对这种情况进行优化。
代码如下
class Solution {
private int[] nums;
// mark[i] = 0 表示nums[i]未使用，mark[i] = 1表示nums[i]已使用
private int[] mark;
private int length;
private List<Integer> tempList;
private List<List<Integer>> resultList;
private StringBuilder stringBuilder;
private Set<String> set;
// 用于对每一次搜索开头的数字做去重
private Set<Integer> numSet;
public List<List<Integer>> permuteUnique(int[] nums) {
length = nums.length;
this.nums = nums;
mark = new int[length];
for (int i = 0; i < length; i++) {
mark[i] = 0;
}
tempList = new ArrayList<>(length);
resultList = new ArrayList<>();
stringBuilder = new StringBuilder();
set = new HashSet<>();
numSet = new HashSet<>(length);
dfsPermute(0);
return resultList;
}
public void dfsPermute(int index) {
if (index == length) {
String str = stringBuilder.toString();
if (!set.contains(str)) {
resultList.add(new ArrayList<>(tempList));
set.add(str);
numSet.add(tempList.get(0));
}
}
for (int i = 0; i < length; i++) {
if (index == 0) {
// 如果numSet中已经有本次搜索开始的第一个数字，continue
if (numSet.contains(nums[i])) {
continue;
} else {
numSet.add(nums[i]);
}
}
if (mark[i] == 0) {
mark[i] = 1;
tempList.add(nums[i]);
String tempStr = String.valueOf(nums[i]) + ",";
stringBuilder.append(tempStr);
dfsPermute(index + 1);
mark[i] = 0;
tempList.remove(tempList.size() - 1);
// 左闭右开
stringBuilder.delete(stringBuilder.length() - tempStr.length(), stringBuilder.length());
}
}
}
}
第二个思路同样AC，耗时46ms，还是太慢，继续优化。
思路三
第二个思路依然存在重复的搜索，以[1,1,2]为例，比如一次搜索以2开头，如果以第一个1作为第二个元素，得到的结果是[2,1,1]，如果以第二个1作为第二个元素，得到的结果还是[2,1,1]。
显然，不仅需要对搜索的第一个元素做去重，第2, 3, .... n 个元素都需要去重，这就是第三个思路。
注意: 第二个思路的numSet是成员变量，第三个思路的numSet是局部变量
代码如下
class Solution {
private int[] nums;
// mark[i] = 0 表示nums[i]未使用，mark[i] = 1表示nums[i]已使用
private int[] mark;
private int length;
private List<Integer> tempList;
private List<List<Integer>> resultList;
private StringBuilder stringBuilder;
private Set<String> set;
public List<List<Integer>> permuteUnique(int[] nums) {
length = nums.length;
this.nums = nums;
mark = new int[length];
for (int i = 0; i < length; i++) {
mark[i] = 0;
}
tempList = new ArrayList<>(length);
resultList = new ArrayList<>();
stringBuilder = new StringBuilder();
set = new HashSet<>();
dfsPermute(0);
return resultList;
}
public void dfsPermute(int index) {
if (index == length) {
String str = stringBuilder.toString();
if (!set.contains(str)) {
resultList.add(new ArrayList<>(tempList));
set.add(str);
}
}
// 每次递归都会创建新的numSet，即对第1,2,3...n个元素，都做了去重
Set<Integer> numSet = new HashSet<>(length);
for (int i = 0; i < length; i++) {
if (mark[i] == 0) {
if (numSet.contains(nums[i])) {
continue;
} else {
numSet.add(nums[i]);
}
mark[i] = 1;
tempList.add(nums[i]);
String tempStr = String.valueOf(nums[i]) + ",";
stringBuilder.append(tempStr);
dfsPermute(index + 1);
mark[i] = 0;
tempList.remove(tempList.size() - 1);
// 左闭右开
stringBuilder.delete(stringBuilder.length() - tempStr.length(), stringBuilder.length());
}
}
}
}
第三个思路也AC了，耗时8ms，还是不够快，继续优化。
思路四
看了好几次代码，想看看哪些操作比较耗时，最后目光定位到了stringBuilder上，假设某个样例的输入数组nums长度是100，总共有1000个符合条件的排列，那么就要拼接100*1000=100000次，这绝对是个巨大的开销!!!
仔细想想，其实第三个思路，已经对第1,2,3...n个元素都做了去重，已经可以保证输出的结果不会重复，所以没有必要对每一个排列都拼接成字符串放进set做去重。
因此第四个思路，就是把stringBuilder去掉
代码如下
class Solution {
private int[] nums;
// mark[i] = 0 表示nums[i]未使用，mark[i] = 1表示nums[i]已使用
private int[] mark;
private int length;
private List<Integer> tempList;
private List<List<Integer>> resultList;
private Set<String> set;
public List<List<Integer>> permuteUnique(int[] nums) {
length = nums.length;
this.nums = nums;
mark = new int[length];
for (int i = 0; i < length; i++) {
mark[i] = 0;
}
tempList = new ArrayList<>(length);
resultList = new ArrayList<>();
set = new HashSet<>();
dfsPermute(0);
return resultList;
}
public void dfsPermute(int index) {
if (index == length) {
resultList.add(new ArrayList<>(tempList));
}
Set<Integer> numSet = new HashSet<>(length);
for (int i = 0; i < length; i++) {
if (mark[i] == 0) {
if (numSet.contains(nums[i])) {
continue;
} else {
numSet.add(nums[i]);
}
mark[i] = 1;
tempList.add(nums[i]);
dfsPermute(index + 1);
mark[i] = 0;
tempList.remove(tempList.size() - 1);
}
}
}
}
第四个思路也AC了，耗时4ms，继续优化。
思路五
继续看代码，寻找耗时的操作，最后目光定位到了numSet。
每一个递归，都要创建numSet，1000次递归，就要创建1000个numSet，这也是个不小的开销，有没有更简单的方法可以代替numSet，实现去重？
其实numSet的作用，遍历nums数组，找第n个元素时，把nums数组中重复的数字去掉。
如果先对nums数组从小到大排序，用一个Integer保存上一次的nums[i]，那么如果nums[i+1]==nums[i]，就表示nums[i+1]是重复的数字，只有nums[i+1]!=nums[i]的时候，才继续搜索。
代码如下
class Solution {
private int[] nums;
// mark[i] = 0 表示nums[i]未使用，mark[i] = 1表示nums[i]已使用
private int[] mark;
private int length;
private List<Integer> tempList;
private List<List<Integer>> resultList;
private Set<String> set;
public List<List<Integer>> permuteUnique(int[] nums) {
length = nums.length;
this.nums = nums;
mark = new int[length];
for (int i = 0; i < length; i++) {
mark[i] = 0;
}
tempList = new ArrayList<>(length);
resultList = new ArrayList<>();
set = new HashSet<>();
Arrays.sort(nums);
dfsPermute(0);
return resultList;
}
public void dfsPermute(int index) {
if (index == length) {
resultList.add(new ArrayList<>(tempList));
}
Integer temp = null;
for (int i = 0; i < length; i++) {
if (mark[i] == 0 ) {
if (temp != null && nums[i] == temp) {
continue;
} else {
temp = nums[i];
}
mark[i] = 1;
tempList.add(nums[i]);
dfsPermute(index + 1);
mark[i] = 0;
tempList.remove(tempList.size() - 1);
}
}
}
}
第五个思路同样AC，耗时2ms。
五次优化的对照表如下
image.png
