本文共 4712 字，大约阅读时间需要 15 分钟。
以下三个题都是LeetCode题库里面的。
1.给定一个没有重复数字的序列，返回其所有可能的全排列。示列： 输入: [1,2,3]输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
整个的过程就如下图，我们可以利用循环让他从第一个元素开始排列，从根开始遍历依次记录节点的值记录在集合之中。
可以根据图可得这是一个回溯算法 1.先去找第一个节点保存他里面的值。 2.再次调用函数 找到去找子集合中不存在的元素并保存（也就是说已经存在的就排除） 3.依次类推，if(size() == num.length)就说明找到第一个排列并保存在集合当中。 4.函数进行回退，删除子集合中的节点。依次类推所有的节点都可求出。 public List
> permute(int[] nums) { List
> list = new ArrayList<>(); List arrayList = new ArrayList<>(); recursion(list,arrayList,nums); return list; } private void recursion(List
> list, List arrayList, int[] nums) { if (nums.length == arrayList.size()){ //返回的条件是说明第n个排列已找到 list.add(new ArrayList (arrayList));//将排列添加集合之中 return ; }else{ for (int i = 0;i < nums.length;i++){ if (!arrayList.contains(nums[i])){ //如果子集合包括num[i],进行下一次的搜索 arrayList.add(nums[i]);//向子集合之中添加搜索到的元素 recursion(list,arrayList,nums); arrayList.remove(arrayList.size() - 1);//删除集合中的元素 } } } }
以上是我对全排列的理解，可能表述的过程有点问题。但是想法肯定是对的。
2.给定一个可包含重复数字的序列，返回所有不重复的全排列。示例:输入: [1,1,2]输出:[[1,1,2],[1,2,1],[2,1,1]]
这个题和第一题的思路总体一样的，只不过这次有重复的元素，所以我们可以使用set集合来保存元素防止重复的元素出现（使用set集合是为了防止排列的重复，set集合的特性：不允许有重复的元素出现）。
eg：1 1 2 这个序列如果用List集合会出现两次的
这里我们需要注意的是重复元素的出现，所谓的重复元素就两个1不能判断那个使用了，那个没使用所以这里必须添加一个等同大小的数组最好是boolen类型的，用于判断重复元素的使用情况。
public List
> permuteUnique(int[] nums) { Set
> set = new HashSet<>(); List list = new ArrayList<>(); boolean[] tag = new boolean[nums.length];//状态数组 Arrays.sort(nums);//对数组进行排序方便处理无序序列 recursion(set,list,nums,tag); List
> lists = new ArrayList(set);//将set集合转换为list集合 return lists; } private void recursion(Set
> set, List list, int[] nums,boolean[] tag) { if (nums.length == list.size()){ set.add(new ArrayList<>(list)); return; }else{ for (int i = 0; i < nums.length; i++) { if (!tag[i]){ //tag初始每个元素都是false，false表示当前元素未进入子集合（注意子集合） list.add(nums[i]); tag[i] = true;//元素添加进去后 recursion(set,list,nums,tag); tag[i] = false; list.remove(list.size() - 1 ); } } } }
什么叫康拓展开？
下式的展开叫做康拓展开：
X=an*(n-1)!+an-1*(n-2)!+…+ai*(i-1)!+…+a21!+a10! ai为整数，并且0<=ai<i(1<=i<=n)，其中ai为小于上一个数字的个数。康拓展开应用在实际的问题之中就是求解第k个排列。
例如：{1,2,3,4} 这个集合之中 2 3 1 4 这个排列表示的是第几个排列组合。-
2 有1个比他小的所以 1*3!
-
3有2个比他小的，但是2已经出现 1*2!
-
1没有比他小的所以 0*1!
-
4有三个比他小的，但是三个都已出现 ，所以0*0!
对上述进行求和可得sum = 8； 所以他是第9个排列。LeetCode里面有一道题就是使用康拓展开来做的给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下："123""132""213""231""312""321"给定 n 和 k，返回第 k 个排列。说明：给定 n 的范围是 [1, 9]。给定 k 的范围是[1, n!]。
这道题就是康拓展开的逆过程，当时看见这道题时挺懵的，因为我第一次写的和上面全排列一样在返回集合里去找第k个排列，代码没有任何问题，就是超时了我也很无奈。
这个方法是我利用上面的思想然后获取到集合转换为数组超时了
public String getPermutation(int n, int k) { String str = ("1,2,3,4,5,6,7,8,9").substring(0,n); List > lists = new ArrayList<>(); List list = new ArrayList<>(); getBake(lists,list,str); String s = new String(); List characters = lists.get(k - 1);//获取指定的第k个集合 Iterator iterator = characters.iterator(); while (iterator.hasNext()){ //通过遍历集合存储在字符串中 Character next = iterator.next(); s += next; } return s; } private void getBake(List > lists, List list, String str) { if (list.size() == str.length()){ lists.add(new ArrayList<>(list)); return; }else{ for (int i = 0; i < str.length(); i++) { if (!list.contains(str.charAt(i))){ list.add(str.charAt(i)); getBake(lists,list,str); list.remove(list.size() - 1); } } } }
康拓排列的逆过程
逆过程就是已知这个数是第k个数，求这个数是多少，当然是知道n的值的。
第k个数就是有k-1个数比这个数小。
所以就是 k-1=an*(n-1)!+an-1*(n-2)!+…+a1*0!;
再举一个例子：
如何找出第16个（按字典序的）{1,2,3,4,5}的全排列？
首先用16-1得到15
用15去除4! 得到0余15
用15去除3! 得到2余3
用3去除2! 得到1余1
用1去除1! 得到1余0
有0个数比它小的数是1，所以第一位是1
有2个数比它小的数是3，但1已经在之前出现过了所以是4
有1个数比它小的数是2，但1已经在之前出现过了所以是3
有1个数比它小的数是2，但1,3,4都出现过了所以是5
最后一个数只能是2
所以排列为1 4 3 5 2
不知道大家能否看的懂这个逆过程，反正我第一次看逆过程的解析，处于完全懵圈状态，真的是混混然，飘飘然，不知其所以然。
其实就是用它的除后的结果去判断当前位置出现的是什么数字。
public String getPermutation(int n, int k) { int[] number = new int[]{ 0,1,2,3,4,5,6,7,8,9}; List list = Arrays.stream(number).boxed().collect(Collectors.toList()); int[] fac = new int[]{ 1,1, 2, 6, 24, 120, 720, 5040, 40320, 362880};//存储1~9的阶乘数 k = k - 1; String str = new String(); while(n > 0){ int value = k / fac[n - 1];//根据公式 除(n-1)! str += list.get(value + 1);//获取value+1是因为list集合之中的第一个元素是0，不是所需排列里面的元素 list.remove(value + 1);//获取完直接删除该元素 k = k % fac[n - 1];//余数 n--; } return str; } 第一次很认真的写文章，可能写的不是很好，但是我会继续改进，坚持写。希望您能点个赞。 如果写的有问题欢迎补充
转载地址：http://nfvo.baihongyu.com/