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].

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    ArrayList<ArrayList<Integer>> result;
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        result = new ArrayList<ArrayList<Integer>>();
		if(num.length==0) {
			return null;
		}
		Arrays.sort(num);
		ArrayList<Integer> list = new ArrayList<Integer>();
		childs(list,num,new boolean[num.length]);
		return result;
    }
    
    //查找list的子节点，可能有多种
	public void childs(ArrayList<Integer> list,int[] num,boolean[] bool) {
		if(list.size()==num.length) {
			//这里一定要new 一个Arra有List，因为result保存的实际上是地址，而list的值最后是一样的而且是最后一步的值（空的），使得最后result的值都是空的，
			//所有要new 一个 复制list的值
			result.add(new ArrayList<>(list));
			return;
		}
		
		//判断num中的数是否有满足list子节点的，子节点的属性包括它自己的值和它的子节点
		for(int i=0;i<num.length;i++) {
			if(bool[i]==true)continue;
			
			if(i>0&&num[i]==num[i-1]&&!bool[i-1])continue;//如果两个相邻的重复元素如1，1只能取一次，那么当走到下标在前面那个1,然后判断1后面的的那个1是否可取时取1，一个list集合就是1，1，
												//当选择第二个1当第一个值，因为for循环时循环所有值，又从下标为0开始选择合适的下一个值，已知已经取了一个1，1list了，那这种就不因该
												//重复，这种不符合的条件是当i>0&&num[i]==num[i-1]&&!bool[i-1]
				bool[i] = true;	
				list.add(num[i]);
				//递归的list会有很多个list的增减变化，在满足条件的list状态节点时就添加进结果中，每进入一个childs算法就是一个list路径
				childs(list, num,bool);
				bool[i] = false;
				//下一个可能值
				list.remove(list.size()-1);
		}
    }
}

通过这道题更加深入了解到了list集合的使用方法。

Array数组和list之间的转换。

list的特点：

    1.数据是有弹性的，可以方便删除和添加，时间复杂度比数组的添加删除低很多。

    2.数据的查找也是很快，contains（）方法可以很快的查到数据是否在list中存在，如果使用数组的话是要用for循环吧，时间复杂度要O(n)

总结，

当一个接口要实现方法的时候，如果输入的类型无法想到解决方式，不妨看看要输出的是什么类型，看看能不能换成输出类型来换种思路解决问题。还有集合真的是高级类型了，很好用，用的好就很高级，脱离初级编程师啦~~~~