-
Notifications
You must be signed in to change notification settings - Fork 0
/
46. Permutations
52 lines (47 loc) · 1.78 KB
/
46. Permutations
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res=new ArrayList<List<Integer>>();
getAll(res, new ArrayList<Integer>(), nums, 0);
return res;
}
public void getAll(List<List<Integer>> res,List<Integer> tempList,int[]nums,int index){
if(index==nums.length-1){
tempList.add(nums[index]);
res.add(new ArrayList<Integer>(tempList));
tempList.remove(tempList.size()-1);
}
for(int i=index;i<=nums.length-1;i++){
swap(nums,i,index);
tempList.add(nums[index]);
getAll(res,tempList,nums,index+1);
tempList.remove(tempList.size()-1);
swap(nums,i,index);
}
}
public void swap(int[]nums,int a,int b){
int temp=nums[a];
nums[a]=nums[b];
nums[b]=temp;
}
思路:全排列就是从第一个数字起每个数分别与它后面的数字交换。
所以每次先将第一个数字与后面的数字置换,添加到list中,然后继续下一次置换,直到index到了最后,说明都置换过了,这样迭代运行之后,所有的置换情况都被考虑到。
运行时间:6ms
另一种回溯的思路:
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
// Arrays.sort(nums); // not necessary
backtrack(list, new ArrayList<>(), nums);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
if(tempList.size() == nums.length){
list.add(new ArrayList<>(tempList));
} else{
for(int i = 0; i < nums.length; i++){
if(tempList.contains(nums[i])) continue; // element already exists, skip
tempList.add(nums[i]);
backtrack(list, tempList, nums);
tempList.remove(tempList.size() - 1);
}
}
}
直接循环迭代,遇见相同的就跳过,不同的记录,到最后都被记录上。