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;

	}

}