原题
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [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/
相关推荐
-
leetcode18-四数之和
原题 给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 ta...
-
leetcode739-每日温度
原题 根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。 例如，给定一个列表 te...
-
剑指offer13-机器人的运动范围
原题（来源Leetcode） 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下...
-
数组元素左右两边最近较小元素
原题（来源牛客网） 给定一个不含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。 实例： 输入: ar...
-
十大排序算法与Java实现
本文参考资源： https://github.com/iTimeTraveler/SortAlgorithms 十大经典排序算法 - 冰狼爱魔 - 博客园 十大经典排序算法总结（J...
-
leetcode66-加一
原题 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外，这个整数不会以...
-
'leetcode50-Pow(x,n)'
原题 实现 pow(x, n) ，即计算 x 的 n 次幂函数。 示例1： 输入： 2.00000, 10 输出： 1024.00000 示例2： 输入： 2.10000, 3 输...
-
leetcode169-多数元素
原题 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例1:...
-
剑指offer05-替换空格
原题（来源Leetcode） 请实现一个函数，把字符串 s 中的每个空格替换成"%20"。 示例1: 输入： s = "We are happy." 输出： "We%20are%2...
-
leetcode445-两数相加II
原题 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。 你可以假设除了数字 0 之外，这两个数字都...
