Permutations II
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].
思路：这题相比于上一题，是去除了反复项。
代码上与上题略有区别。详细代码例如以下：
public class Solution {
boolean[] b;
List<List<Integer>> list;
Set<String> al;
public List<List<Integer>> permuteUnique(int[] nums) {
b = new boolean[nums.length];
Arrays.fill(b,true);
Arrays.sort(nums);
list = new ArrayList<List<Integer>>();
al = new HashSet<String>();
count(nums, "", nums.length);
//对al数据进行处理
Iterator<String> iterator = al.iterator();
//迭代器
while(iterator.hasNext()){
String s = iterator.next();
List<Integer> newal = new ArrayList<Integer>();
for(int i = 0; i < s.length();i++){
if(s.charAt(i) == '-'){//有负号
newal.add('0' - s.charAt(++i) );
}else{//无负号
newal.add(s.charAt(i) - '0');
}
}
list.add(newal);
}
return list;
}
/**
* @param nums 要排列的数组
* @param str 已经排列好的字符串
* @param nn 剩下须要排列的个数，假设须要全排列，则nn为数组长度
*/
void count(int[] nums,String str,int nn){
if(nn == 0){
al.add(str);//先加入到al中，再对al数据进行处理
return;
}
for(int i = 0; i < nums.length; i++){
if(nn == nums.length && i > 0 && nums[i] == nums[i-1]){
continue;//去除反复项
}
if(b[i]){//假设还没有组合，则组合上
b[i] = false;//标记为已组合
count(nums,str + nums[i],nn-1);
b[i] = true;//为下一组合准备
}
}
}
}
可是上述代码在数据量比較大的时候效率非常低，如数据有10个数据时大概耗时200ms。在论坛上看到了一个大神的代码。10个数据的耗时约25ms,效率非常高。
详细代码例如以下：
public class Solution {
public List<List<Integer>> permuteUnique(int[] num) {
List<List<Integer>> returnList = new ArrayList<List<Integer>>();
returnList.add(new ArrayList<Integer>());
for (int i = 0; i < num.length; i++) {
Set<List<Integer>> currentSet = new HashSet<List<Integer>>();
for (List<Integer> l : returnList) {
for (int j = 0; j < l.size() + 1; j++) {
l.add(j, num[i]);
List<Integer> T = new ArrayList<Integer>(l);
l.remove(j);
currentSet.add(T);
}
}
returnList = new ArrayList<List<Integer>>(currentSet);
}
return returnList;
}
}