Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].
解题思路一：
发现Java for LeetCode 046 Permutations自己想多了，代码直接拿来用，结果Time Limit Exceeded！看来还是不能直接用
解题思路二：
修改上述代码，去掉set，改用List，修改如下：
static public List<List<Integer>> permuteUnique(int[] nums) {
ArrayList<List<Integer>> set=new ArrayList<List<Integer>>();
dfs(set,nums,0);
return set;
}
static List<Integer> list=new ArrayList<Integer>();
static public void dfs(List<List<Integer>> set,int[] nums,int depth){
if(depth==nums.length){
set.add(new ArrayList<Integer>(list));
return;
}
for(int i=0;i<=depth;i++){
while(i<depth&&nums[depth]==list.get(i))
i++;
list.add(i,nums[depth]);
dfs(set,nums,depth+1);
list.remove(i);
}
}
结果还是Time Limit Exceeded！看来不排序直接DFS这条路是走不通了。
解题思路三：
既然不排序直接DFS走不通，因此，可以考虑排序后，然后以字典的方式进行全排列添加，考虑到在Java for LeetCode 031 Next Permutation题目中，我们已经写了一个字典的排列，稍作修改，添加boolean类型的返回值即可拿来用，JAVA实现如下：
static public List<List<Integer>> permuteUnique(int[] nums) {
ArrayList<List<Integer>> set=new ArrayList<List<Integer>>();
Arrays.sort(nums);
do{
List<Integer> list=new ArrayList<Integer>();
for(int num:nums)
list.add(num);
set.add(list);
}while(nextPermutation(nums));
return set;
}
static public boolean nextPermutation(int[] nums) {
int index = nums.length - 1;
while (index >= 1) {
if (nums[index] > nums[index - 1]) {
int swapNum=nums[index-1],swapIndex = index+1;
while (swapIndex <= nums.length - 1&& swapNum < nums[swapIndex])
swapIndex++;
nums[index-1]=nums[swapIndex-1];
nums[swapIndex-1]=swapNum;
reverse(nums,index);
return true;
}
index--;
}
reverse(nums,0);
return false;
}
static void reverse(int[] nums,int swapIndex){
int[] swap=new int[nums.length-swapIndex];
for(int i=0;i<swap.length;i++)
swap[i]=nums[nums.length-1-i];
for(int i=0;i<swap.length;i++)
nums[swapIndex+i]=swap[i];
}
结果Accepted！