原题
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]
解法
思想
这道题和leetcode46-全排列的区别在于，数组中会出现相同的数字，对于搜索来说，我们把它想象成树的DFS搜索，就应该避免在同一层搜索到相同值的节点，而不同层之间是允许存在相同值节点的。
我们使用上道题的代码进行改造，如下所示：
代码
class Solution {
List<List<Integer>> ans = new ArrayList<>();
int[] nums;
public List<List<Integer>> permuteUnique(int[] nums) {
int[] used = new int[nums.length];
this.nums = nums;
//要去重，先排序
Arrays.sort(nums);
List<Integer> list = new ArrayList<>();
dfs(list,used,0);
return ans;
}
public void dfs(List<Integer> list,int[] used,int usedCount){
if(usedCount==nums.length){
ans.add(list);
}
for(int i = 0;i<nums.length;i++){
// i == 0，前面没有元素，可以搜索
// used[i-1] == 0，前面的元素在别的层级用过了，可以搜索
// nums[i]!=nums[i-1]，前面的元素和当前元素不相同，可以搜索
if(used[i]==0 && (i == 0 || used[i-1] ==1 || nums[i]!=nums[i-1])){
List<Integer> copy = new ArrayList<>(list);
copy.add(nums[i]);
int[] usedCopy = Arrays.copyOf(used,used.length);
usedCopy[i] = 1;
dfs(copy,usedCopy,usedCount+1);
}
}
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode47-%e5%85%a8%e6%8e%92%e5%88%97ii/
相关推荐
-
leetcode36-有效的数独
原题 判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-...
-
leetcode658-找到K个最接近的元素
原题 给定一个排序好的数组，两个整数 k 和 x，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。如果有两个数与 x 的差值一样，优先选择数值较...
-
leetcode35-搜索插入位置
原题 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 你可以假设数组中无重复元素。 示例 1: 输入: [...
-
leetcode38-外观数列
原题 「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下： 1. 1 2. 11 3. 21 4. 1211 5. 111221 1 被读作...
-
leetcode403-青蛙过河
原题 一只青蛙想要过河。 假定河流被等分为 x 个单元格，并且在每一个单元格内都有可能放有一石子（也有可能没有）。 青蛙可以跳上石头，但是不可以跳入水中。 给定石子的位置列表（用单...
-
leetcode221-最大正方形
原题 在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。 示例: 输入: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 ...
-
使用递归函数逆序一个栈
原题（来源：牛客网） 一个栈依次压入1,2,3,4,5那么从栈顶到栈底分别为5,4,3,2,1。将这个栈转置后，从栈顶到栈底为1,2,3,4,5，也就是实现了栈中元素的逆序，请设计...
-
蓝桥杯试题-大小写转换
原题 资源限制 时间限制：1.0s 内存限制：256.0MB 问题描述 输入一个字符串，将大写字符变成小写、小写变成大写，然后输出 输入格式 acbAB 输出格式 ACBab ...
-
leetcode23-合并K个排序链表
原题 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入： [ 1->4->5, 1->3->4, 2->6 ] 输出： 1->1->2->3->...
-
leetcode136-只出现一次的数字
原题 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 说明： 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗...
