摘要：题目详情题目要求输入一个可能会有重复数字的数组，要求我们输出可能组成的全排列无重复排列。可以用来实现，但这种实现方式复杂度高。另外一种实现思路是，新声明一个数组来存储中元素的使用状况。以这个数组为例。
题目详情
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
题目要求输入一个可能会有重复数字的数组nums，要求我们输出nums可能组成的全排列（无重复排列）。
思路
这道题和 46题全排列 的差别就在于它可能存在重复数字，所以我们就要考虑重复数字可能造成的重复排列的问题。
一种思路就是我在没次为我的结果集res添加新的排列的时候 判断新添加的排列 是否已经存在于结果集中了。可以用hashset来实现，但这种实现方式复杂度高。
另外一种实现思路是，新声明一个boolean数组isUsed来存储nums中元素的使用状况。然后在生成当前排列curr的时候就避免重复排列的产生。
以[1,1*,2]这个数组为例。
对于每次遍历的元素nums[i]，我们要判断它是否等于nums[i-1]，如果相等而且nums[i-1]被使用过的话，就可以组成一个未出现的排序(eg.[1，1])，如果nums[i-1]未被使用过，那么我们不会将nums[i]添加进排列，避免产生[1,1]这样的重复排列。
解法
public List> permuteUnique(int[] nums) {
List> res = new ArrayList>();
boolean[] isUsed = new boolean[nums.length];
List curr = new ArrayList();
Arrays.sort(nums);
backtrack(res,isUsed,curr,nums);
return res;
}
public void backtrack(List> res,boolean[] isUsed,List curr,int[] nums){
if(nums.length == curr.size()){
res.add(new ArrayList(curr));
return;
}
for(int i=0;i0 && nums[i] == nums[i-1] && !isUsed[i-1])continue;
isUsed[i] = true;
curr.add(nums[i]);
backtrack(res,isUsed,curr,nums);
isUsed[i] = false;
curr.remove(curr.size()-1);
}
}
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/71098.html
