大家好,又见面了,我是你们的朋友全栈君。
给定一个没有重复数字的序列,返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
无奈,用swap的方法从左向右滑动,直到最后结果和最初的一致停止,只适用于三位数。。。。(改进一下让每个数字作为第一位后面的进行滑动,应该可以pass,放弃)
错:
1 class Solution {
2 public static void swap(int[] nums_,int a,int b){
3 int temp = nums_[a];
4 nums_[a] = nums_[b];
5 nums_[b] = temp;
6 }
7 public static boolean isEqual(int[] a,int[] b){
8 for(int i = 0;i < a.length;i++){
9 if(a[i] != b[i])return false;
10 }
11 return true;
12 }
13 public List<List<Integer>> permute(int[] nums) {
14 List<List<Integer>> res = new ArrayList();
15 List<Integer> lists = new ArrayList();
16 if(nums.length < 2){
17 lists.add(nums[0]);
18 res.add(lists);
19 return res;
20 }
21 int[] nums_ = new int[nums.length];
22 for(int k = 0;k < nums.length;k++){
23 nums_[k] = nums[k];
24 lists.add(nums[k]);
25
26 }
27 res.add(new ArrayList(lists));
28 lists.removeAll(lists);
29 swap(nums_,0,1);
30 for(int j = 0;j < nums.length;j++){
31 lists.add(nums_[j]);
32 }
33 res.add(new ArrayList(lists));
34 int i = 1;
35 while(!isEqual(nums,nums_)){
36 if(i+1<nums.length){
37 swap(nums_,i,i+1);
38 if(!isEqual(nums,nums_)){
39 lists.removeAll(lists);
40 for(int j = 0;j < nums.length;j++){
41 lists.add(nums_[j]);
42 }
43 res.add(new ArrayList(lists));
44 }
45 i++;
46 }else{
47 i = 0;
48 }
49 }
50 return res;
51 }
52
53 }
正确做法bt: 添加顺序就是[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]
[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2],
[2, 1, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1],
[3, 1, 2, 4], [3, 1, 4, 2], [3, 2, 1, 4], [3, 2, 4, 1], [3, 4, 1, 2], [3, 4, 2, 1],
[4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 1, 2], [4, 3, 2, 1]]
TIME:O(N!*N)(整体来说)
SPACE:O(N)
1 class Solution {
2
3 public List<List<Integer>> permute(int[] nums) {
4 List<List<Integer>> res = new ArrayList<>();
5 if(nums== null || nums.length ==0)return res;
6 helper(res,new ArrayList<>(),nums);
7 return res;
8 }
9 public void helper(List<List<Integer>> res,List<Integer> list,int[] nums){
10 if(list.size() == nums.length){
11 res.add(new ArrayList<>(list));
12 return;
13 }
14 for(int i = 0;i < nums.length;i++){
15 if(list.contains(nums[i]))continue;//contaisn的时间复杂度为O(N)
16 list.add(nums[i]);
17 helper(res,list,nums);
18 list.remove(list.size()-1);
19 }
20 }
21
22 }
如果递归符合T(n) = T(n-1)+T(n-2)+….T(1)+T(0) 时间复杂度基本符合O(2^n),如果在其中的一些步骤可以省略,则可以简化为O(n!)
对于方法1思想的完善:
TIME:O(N)
SPACE:O(N)
1 class Solution {
2
3 public List<List<Integer>> permute(int[] nums) {
4 List<List<Integer>> res = new ArrayList<>();
5 if(nums.length == 0 || nums == null)return res;
6 helper(res,0,nums);
7 return res;
8 }
9 public void helper(List<List<Integer>> res,int start,int[] nums){
10 if(start == nums.length){
11 List<Integer> list = new ArrayList<>();
12 for(int q:nums){
13 list.add(q);
14 }
15 res.add(new ArrayList<>(list));
16 return;
17 }
18 for(int i = start;i < nums.length;i++){
19 swap(nums,start,i);
20 helper(res,start+1,nums);
21 swap(nums,start,i);
22 }
23
24 }
25 public void swap(int[] nums,int l,int m){
26 int temp = nums[l];
27 nums[l] = nums[m];
28 nums[m] = temp;
29 }
30
31 }
2019-05-04 10:45:10
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/155567.html原文链接:https://javaforall.cn