Permutations IIGiven 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;}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
只要有信心，人永远不会挫败
