Lintcode 15 全排列
给定一个数字列表,返回其所有可能的排列。
注意事项 你可以假设没有重复数字。
思路:思路:n个数字额全排列等于将最后一个数字k插入前n-1个数的全排列中,
【给定一个数字列表,返回其所有可能的排列。 注意事项 你可以假设没有重复数字。】这就是递归思想
int类型的nums数组作为输入
1.当只有一个数时输出这个数的排列
2.否则将这个nums的前n-1个数赋值到array数组中
3.递归调用返回排列,本代码中返回List
4.对List中的每一个排列构造全排列
public class Solution {
/*
* @param nums: A list of integers.
* @return: A list of permutations.
*/
public List> permute(int[] nums) {
//用来存放nums前n-1个数
int[] array=null;
//n表示nums数组的最后一个数
int n = 0;
//array数组的长度
int array_len = nums.length-1;
List
List> list = new ArrayList
>();
if(nums==null||nums.length==0){
list.add(num);
return list;
}
//当只有一个数时,输出这个排列
if(nums.length==1){
num.add(nums[0]);
list.add(num);
return list;
}else{
//将这n个数的前n-1个数存到array数组中
array = new int[array_len];
for(int i = 0;
iarray[i]=nums[i];
}
//递归调用函数返回全排列的List
list = permute(array);
//size表示第n个数插入前list的大小
int size = list.size();
//对list中的每一个排列构造全排列
for(int j=0;
j//num表示list中的一个排列
num = list.get(j);
//num_size表示list的一个排列也就是num的大小
int num_size = num.size();
//将第n个数插入到前n-1个数的各个不同的位置,从0到num_size
for(int k = 0;
k<=num_size;
k++){
//不能直接赋值,否则temp是num的引用,对temp的操作也就是对num的操作
List
// List
//temp.addAll(num);
n = nums[array_len];
temp.add(k,n);
list.add(temp);
}
}
//第n个数插入到前n-1个排列之后够成n个数的全排列,要移除插入前的排列,每次移除首位
for (int i = 0;
i < size;
i++) {
list.remove(0);
}
return list;
}
}
}
当有重复的全排列时,只要在list.add(temp);
做如下修改即可
if(list.contains(temp))
continue;
else
list.add(temp);
版权所有:转载请注明出处!