题解 | #没有重复项数字的全排列#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型一维数组 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> permute (int[] num) {
        ArrayList<ArrayList<Integer>>  list= new ArrayList<ArrayList<Integer>> ();
        ArrayList<Integer> item=new ArrayList<Integer>();
        ArrayList<Integer> t;
        item.add(num[0]);
        list.add(item);
        //遍历要依次插入的数字
        for(int n=1;n<num.length;n++){
            //把该轮插入新数字的数字添加到addlist集合里
            ArrayList<ArrayList<Integer>>  addlist= new ArrayList<ArrayList<Integer>> ();
            // 对list集合的数组进行遍历
            for(int i=0;i<list.size();i++){
                item=new ArrayList<Integer>(list.get(i));
                //在数组尾部插入数字
                t=new ArrayList<Integer>(item);
                t.add(num[n]);
                addByOrder(addlist,t);
                //对数组进行不同位置进行遍历插入新数字，然后按字典顺序进行插入到addlist集合里
                for(int j=item.size()-1;j>=0;j--){
                    t=new ArrayList<Integer>(item);
                    t.add(j,num[n]);
                    addByOrder(addlist,t);
                }
            }
            list=addlist;
        }
        return list;
    }
    //在加入集合的时候按字典顺序进行插入
    public void addByOrder(ArrayList<ArrayList<Integer>> list,ArrayList<Integer> tar){
        boolean flg=true;
        for(int i=0;i<list.size();i++){
            ArrayList<Integer> item=list.get(i);
            for(int j=0;j<item.size();j++){
                if(tar.get(j)<item.get(j)){
                    list.add(i,tar);
                    return;
                }else{
                    break;
                }
            }
        }
        if(flg){
            list.add(tar);
        }
    }
}