Version: Next
47.全排列2
难度 中等
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
示例 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
DFS
与 46 题的区别
按照 46 题的解法，答案实际上正确的，只不过答案中包含重复结果
- 要进行
去重处理
如何去重
使用 contains 方法筛选
- 在向最终结果集中添加结果时，先判断结果是不是已经存在过了
- 非常好实现，但是非常耗时
基于数组比较
- 写一个方法，比较即将要被比较的那个值，是不是之前已经出现过
- 在 [depth, current) 之间有没有与 current 重复的元素，就是用 i 遍历这个区间，比较 nums[i] 与 nums[current] 的值
- 精髓是，在 DFS 的每一层，保证某元素只出现过一次，除了深度位置以外的位置，元素顺序根本不重要，可以全部剔除，因为它们最终排列组合的结果是一致的
public class _47全排列2 {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> resultList = new ArrayList<>();
if (nums.length == 1) {
resultList.add(Collections.singletonList(nums[0]));
return resultList;
}
dfs(0, nums, resultList);
return resultList;
}
private void dfs(int depth, int[] nums, List<List<Integer>> resultList) {
if (depth == nums.length) {
// 找到了一个解，添加到结果集
List<Integer> singleResList = new ArrayList<>();
for (int n : nums)
singleResList.add(n);
resultList.add(singleResList);
return;
}
// 枚举当前层所有的选择
// 从当前层 对应数值的下标开始遍历 ， 因为之前的位置已经选定了
for (int i = depth; i < nums.length; i++) {
if (isRepeat(nums, depth, i)) continue;
swap(nums, depth, i);
dfs(depth + 1, nums, resultList);
swap(nums, depth, i); // 回溯 恢复现场
}
}
/**
* 判断即将要交换的值之前是不是已经出现过，是不是重复的
*
* @param nums 数组
* @param depth 当前深度
* @param current 当前元素下表
* @return 即将要交换的当前元素是不是已经出现过
*/
private boolean isRepeat(int[] nums, int depth, int current) {
for (int i = depth; i < current; i++)
if (nums[current] == nums[i]) return true;
return false;
}
private void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
public static void main(String[] args) {
int[] nums = {1, 1, 3};
_47全排列2 obj = new _47全排列2();
List<List<Integer>> permute = obj.permuteUnique(nums);
for (List<Integer> integers : permute) {
for (Integer integer : integers)
System.out.print(integer + ", ");
System.out.print("\n");
}
}
}