给定一个数字列表,返回其所有可能的排列。 注意事项 你可以假设没有重复数字。

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 num = new ArrayList();
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 temp= new ArrayList(num);
// List temp= new ArrayList();
//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);


版权所有:转载请注明出处!

    推荐阅读